?很簡單的搜索題目,隨便寫。
也能枚舉,因為每個點翻轉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 }
poj1741??