四川建设厅官方网站查询,制作自己的网站教程,如何做网站的关键词排名,珠海市官网网站建设价格正题
题目链接:https://jzoj.net/senior/#contest/show/3011/1 题目大意 n∗mn*mn∗m的格子#xff0c;格子之间有道路#xff0c;对于每个iii就走过最短的回路使得
圈住iii个有价值的格子没有圈住任何一个坏格子 解题思路
判断一个点是否在一个多边形内#xff0c;我们可…正题
题目链接:https://jzoj.net/senior/#contest/show/3011/1 题目大意
n∗mn*mn∗m的格子格子之间有道路对于每个iii就走过最短的回路使得
圈住iii个有价值的格子没有圈住任何一个坏格子 解题思路
判断一个点是否在一个多边形内我们可以往任何一个方向画一条射线如果与多边形的交点为奇数那么就在否则就不在。
那么我们考虑状态压缩fi,j,sf_{i,j,s}fi,j,s表示走到(i,j)(i,j)(i,j)这个位置往上画线的交点为奇数的有用点格子集合为sss。
然后bfsbfsbfs转移即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define lowbit(x) (x-x)
using namespace std;
const int dx[4]{1,0,-1,0},dy[4]{0,1,0,-1};
struct point{int x,y,s;
}val[50],no[50];
queuepoint q;
int n,m,cnt1,cnt2,ans[50],f[55][55][1500];
char c[55];
int count_one(int x)
{int ans0;while(x){ans;x-lowbit(x);}return ans;
}
int main()
{freopen(data.txt,r,stdin);cnt1cnt2-1;while(scanf(%s,c1)!EOF){n;mstrlen(c1);for(int j1;jm;j){if(c[j]I)val[cnt1](point){n,j};if(c[j]X)no[cnt2](point){n,j};}}memset(f,0x3f,sizeof(f));f[0][0][0]0;q.push((point){0,0,0});while(!q.empty()){int xq.front().x,yq.front().y,sq.front().s;q.pop();for(int k0;k4;k){int zxxdx[k],zyydy[k];if(zx0||zxn||zy0||zym) continue;int tmps;if(k1){for(int j0;jcnt1;j)if(val[j].yy1val[j].xx1) tmp^(1j); for(int j0;jcnt2;j)if(no[j].yy1no[j].xx1) tmp^(1jcnt11); }if(k3){for(int j0;jcnt1;j)if(val[j].yyval[j].xx1) tmp^(1j); for(int j0;jcnt2;j)if(no[j].yyno[j].xx1) tmp^(1jcnt11); }if(f[x][y][s]1f[zx][zy][tmp]){q.push((point){zx,zy,tmp});f[zx][zy][tmp]f[x][y][s]1;}}}memset(ans,0x3f,sizeof(ans));cnt1;for(int i0;i(1cnt1);i){int dcount_one(i);ans[d]min(ans[d],f[0][0][i]);}for(int i1;icnt1;i)printf(%d\n,ans[i]);
}
