首页 > 代码库 > POJ 1753 Flip Game 简单BFS
POJ 1753 Flip Game 简单BFS
很简单的搜索题目,随便写。
题目链接
1 #include <stdio.h> 2 #include <string.h> 3 int st; 4 char s[10]; 5 int q[70000],vis[70000],front,tail; 6 const int dx[]={1,-1,0,0}; 7 const int dy[]={0,0,1,-1}; 8 int BFS() { 9 front=tail=0;10 memset(vis,-1,sizeof(vis));11 q[tail++]=st;12 vis[st]=0;13 while (front!=tail) {14 int u=q[front++];15 if (!u||u==65535)16 return vis[u];17 for (int x=0;x<4;x++)18 for (int y=0;y<4;y++) {19 int v=u;20 v^=1<<((x<<2)+y);21 for (int j=0;j<4;j++) {22 int nx=x+dx[j],ny=y+dy[j];23 if (0<=nx&&nx<4&&0<=ny&&ny<4) {24 v^=1<<((nx<<2)+ny);25 }26 }27 if (vis[v]==-1) {28 vis[v]=vis[u]+1;29 q[tail++]=v;30 }31 }32 }33 return -1;34 }35 36 int main() {37 while (~scanf("%s",s)) {38 st=0;39 for (int i=0;i<4;i++)40 st=st<<1|(s[i]==‘b‘);41 for (int j=0;j<3;j++) {42 scanf("%s",s);43 for (int i=0;i<4;i++)44 st=st<<1|(s[i]==‘b‘);45 }46 int ans=BFS();47 if (ans==-1)48 puts("Impossible");49 else50 printf("%d\n",ans);51 }52 return 0;53 }
POJ 1753 Flip Game 简单BFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。