只有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;
}