首页 > 代码库 > 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 }
View Code

 

POJ 1753 Flip Game 简单BFS