poj 2965 The Pilots Brothers refrigerator[ 枚举 ]

传送门：?id=2965

思路：二进制枚举，递归输出路径。G++ 900+Ms勉强过，，C++超时。

代码：

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<stack>#include<map>#define INF 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int N=100007;int vis[N];int step[N][4];int change(int state,int i,int j){for(int k=0;k<4;k++){state=state^1<<(4*k+j);state=state^1<<(4*i+k);}state=state^1<<(i*4+j);return state;}void output(int state){if(step[state][0]==0)return;else{output(step[state][1]);printf("%d %d\n",step[state][2],step[state][3]);}}void bfs(int state){queue<int> que;que.push(state);while(!que.empty()){int cur=que.front();que.pop();if(cur==65535){printf("%d\n",step[65535][0]);output(65535);break;}for(int i=0;i<4;i++){for(int j=0;j<4;j++){int tmp=change(cur,i,j);if(!vis[tmp]){vis[tmp]=1;step[tmp][0]=step[cur][0]+1;step[tmp][1]=cur;step[tmp][2]=i+1;step[tmp][3]=j+1;que.push(tmp);}}}}}int main(){//mem(vis,0);//mem(step,0);int state=0;for(int i=0;i<16;i++){char c;cin>>c;if(c=='-'){state=state|1<<i;}}vis[state]=1;bfs(state);return 0;}

人只要不失去方向，就不会失去自己