//位压缩加搜索枚举,用pre记录其前驱 #include<stdio.h> #include<string.h> #define N 100000 struct node { int x,y,num,pre,step; }p[N*4]; struct nn { int x,y; }g[N*4]; char str[10][10]; int vis[N]; int d[16]= { 0xf888,0xf444,0xf222,0xf111, 0x8f88,0x4f44,0x2f22,0x1f11, 0x88f8,0x44f4,0x22f2,0x11f1, 0x888f,0x444f,0x222f,0x111f, }; int bfs(int sum) { int head=0,tail=0,i; p[head].num=sum; p[head].step=0; p[head].pre=0; tail++; while(head<tail) { int k=p[head].num; for(i=0;i<16;i++) { int x=k^d[i]; if(vis[x]==0) { vis[x]=1; p[tail].num=x; p[tail].x=i/4; p[tail].y=i%4; p[tail].pre=head; p[tail].step=p[head].step+1; if(x==0){ return tail;} tail++; } } head++; } return 0; } int main() { int i,j; memset(vis,0,sizeof(vis)); for(i=0;i<4;i++) { scanf("%s",str[i]); } int sum=0; for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(str[i][j]=='+') { sum<<=1; sum+=1; } else { sum<<=1; } } } if(sum==0){printf("0\n");return 0;} int ans=bfs(sum); printf("%d\n",p[ans].step); i=0; g[i].x=p[ans].x; g[i].y=p[ans].y;//注意这,可能只需一次就可以开锁 while(p[ans].pre) { //printf("%d %d\n",p[ans].x,p[ans].y); i++; ans=p[ans].pre; if(ans==0)break; g[i].x=p[ans].x; g[i].y=p[ans].y; } for(;i>=0;i--) { printf("%d %d\n",g[i].x+1,g[i].y+1); } }