这题与1753点灯游戏很类似,只不过变换状态的方式不一样罢了..
状态压缩+BFS就可以解决,与1753不同的就是要记录路径,可以通过给队列中的元素加上pre和next属性来实现.
运行时间690MS,感觉挺慢的,后来在dicuss里看到了一位大牛的总结,很好的方法啊..有时候做题前多思考真的是很重要啊,即使是对一些很面熟的题目.
“先看一个简单的问题,如何把'+'变成'-'而不改变其他位置上的状态?答案是将该位置(i,j)及位置所在的行(i)和列(j)上所有的handle更新一次,结果该位置被更新了7次,相应行(i)和列(j)的handle被更新了6次,剩下的被更新了4次.被更新偶数次的handle不会造成最终状态的改变.因此得出高效解法,在每次输入碰到'+'的时候,自增该位置与相应的行和列,当输入结束后,遍历数组,所有为奇数的位置则是操作的位置,而奇数位置的个数之和则是最终的操作次数.”,
#include <cstdio> #include <string.h> using namespace std; struct record{ int va,pre,next,c;//分别记录当前状态,前驱,后继,和操作 }r[70000]; int vi[70000];//是否访问 int st;//起始状态 int f(int x,int i){//位运算更改状态 x^=1<<i;//更改当前格 int lx=i/4,ly=i%4; //获取行,列 for(int j=0;j<4;j++){ x^=1<<(4*j+ly);//更改列 x^=1<<(4*lx+j);//更改行 } return x; } void solve(int pos){ int a,b,res=1; int head=pos; while(r[head].pre!=0){//根据前驱向前找直到起始点, 记录变换次数和后驱 r[r[head].pre].next=head; head=r[head].pre; res++; } printf("%d\n",res); for(int i=0;i<res;i++){ //根据后驱和变换次数进行输出 printf("%d %d\n",r[head].c/4+1,r[head].c%4+1); head=r[head].next; } } void bfs(int x){ if(x==0)return; int front=0,tail=0; r[0].va=x; vi[x]=1; tail++; while(1){ int v=r[front].va; for(int i=0;i<16;i++){ int ns=f(v,i); if(vi[ns]==0){ r[tail].va=ns; r[tail].pre=front; r[tail].c=i; if(ns==0){//找到结果 solve(tail); return; } vi[ns]=1; tail++; } } front++; } } int main(){ char line[6]; st=0; for(int i=0;i<4;i++){ scanf("%s",line); for(int j=0;j<4;j++){ if(line[j]=='+')st+=1<<(4*i+j); } } memset(vi,0,sizeof vi); bfs(st); return 0; }