只有4*4大小的0/1矩阵, 很容易想到转成一个二进制数放进int作为状态, 就可以直接暴搜了.
此题POJ评测不是一般的坑, 选C++TLE, 选G++AC.
#include<cstdio> #include<queue> #define re register #define in inline using namespace std; in int read() { int s(0),b(0);char ch; do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9'); while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); if(b) return -s; return s; } struct node{int v,step;}; queue<node> q; int b[130000],pre[130000][2];//pre[sta][0]表示状态sta的前驱状态(由于不会重复搜索一个状态,所以每个状态的前驱唯一), [1]存放此步操作的坐标. in void cg(int &t,int h,int l) { for(re int j=1;j<=4;++j) t=t^(1<<((h-1)*4+j-1)); for(re int i=1;i<=4;++i) t=t^(1<<((i-1)*4+l-1)); t=t^(1<<((h-1)*4+l-1)); }//对(h,l)进行操作 in int bfs() { while(!q.empty()) { node now=q.front(); q.pop(); for(re int i=1;i<=4;++i) { for(re int j=1;j<=4;++j) { node t=now; cg(t.v,i,j); if(b[t.v]) continue; pre[t.v][0]=now.v,pre[t.v][1]=(i-1)*4+j;//记录路径 if(t.v==0) return t.step+1; b[t.v]=1,++t.step; q.push(t); } } } } in void out(int sta) { if(pre[sta][0]!=-1) out(pre[sta][0]); else return; printf("%d %d\n",(pre[sta][1]-1)/4+1,(pre[sta][1]-1)%4+1); } signed main() { int st=0; char str[5]; for(re int i=1;i<=4;++i) { scanf("%s",str); for(re int j=0;j<4;++j) if(str[j]=='+') st=st|(1<<((i-1)*4+j)); } if(!st){printf("0\n");return 0;} b[st]=1; pre[st][0]=-1; node t; t.v=st,t.step=0; q.push(t); printf("%d\n",bfs()); out(0); return 0; }
最新评论