我是蒟蒻，所以我只会打一个暴力。
这道题就是状压+暴力Bfs，（~~连双向Bfs优化都不用，跟别说A*什么的了~~）
Code
#include<bits/stdc++.h> #define MAXBIT 150007 using namespace std; bool vis[MAXBIT]; struct Node { int state,step; }; struct Pre { int state,x,y; }pre[MAXBIT]; void print_ans(int state) { if(pre[state].state==-1) { return ; } print_ans(pre[state].state); printf("%d %d\n",pre[state].x,pre[state].y); } void Bfs(int s,int t) { //Ô´µã£¬ÖÕµã if(s==0) { puts("0"); return ; } queue<Node> q; int val[5][5],tmp[5][5]; //tp=tempÊÇÁÙʱÊý×é vis[s] = 1; q.push((Node){s,0}); while(!q.empty()) { int now = q.front().state ,step = q.front().step; q.pop(); memset(val,0,sizeof(val)); int tmpnow = now; for(int i=4;i>=1;--i) for(int j=4;j>=1;--j) { val[i][j] = tmpnow & 1; tmpnow >>= 1; } //test for(int x=1;x<=4;++x) for(int y=1;y<=4;++y) { memset(tmp,0,sizeof(tmp)); for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) tmp[i][j] = val[i][j]; for(int i=1;i<=4;++i) { tmp[x][i] ^= 1; tmp[i][y] ^= 1; } tmp[x][y] ^= 1; int nst = 0; //new state for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) { nst = (nst<<1) + tmp[i][j]; } if(!vis[nst]) { vis[nst] = 1; pre[nst].state = now; pre[nst].x = x; pre[nst].y = y; q.push((Node){nst,step+1}); } if(nst == 0) { printf("%d\n",step+1); print_ans(nst); return ; } } } } int main() { char ch; int s=0; for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) { scanf(" %c",&ch); s = (s<<1) + (ch=='+' ? 1 : 0); //Ä¿±ê¾ÍÊÇȫΪÁã } pre[s].state = -1; Bfs(s,0); return 0; }转载于:https://www.cnblogs.com/BaseAI/p/11438875.html
