poj1741，POJ 1753 Flip Game 簡單BFS

2023-11-19 阅读 30 评论 0

摘要：?很簡單的搜索題目，隨便寫。也能枚舉，因為每個點翻轉2次和不翻轉沒區別，所以可以枚舉每個點翻轉或者不翻轉題目鏈接 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

?很簡單的搜索題目，隨便寫。

也能枚舉，因為每個點翻轉2次和不翻轉沒區別，所以可以枚舉每個點翻轉或者不翻轉

題目鏈接

 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^1<<((x<<2)+y);
20         for (int j=0;j<4;j++) {
21           int nx=x+dx[j],ny=y+dy[j];
22           if (0<=nx&&nx<4&&0<=ny&&ny<4) {
23             v^=1<<((nx<<2)+ny);
24           }
25         }
26         if (vis[v]==-1) {
27           vis[v]=vis[u]+1;
28           q[tail++]=v;
29         }
30       }
31   }
32   return -1;
33 }
34 
35 int main() {
36   while (~scanf("%s",s)) {
37     st=0;
38     for (int i=0;i<4;i++)
39       st=st<<1|(s[i]=='b');
40     for (int j=0;j<3;j++) {
41       scanf("%s",s);
42       for (int i=0;i<4;i++)
43         st=st<<1|(s[i]=='b');
44     }
45     int ans=BFS();
46     if (ans==-1)
47       puts("Impossible");
48     else
49       printf("%d\n",ans);
50   }
51   return 0;
52 }