poj2965_refrigerator(BFS+枚举)

本文主要是介绍poj2965_refrigerator(BFS+枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

结题思想：
1.此题一定要使用枚举，将每一个位置的值变化的可能都枚举一下。但是个要么变，要么不变，并且和改变的顺序无关。（具体的证明我还不是很清楚，希望看到博客的朋友，如果知道怎么证明，请不吝赐教）。
2.要找最少的情况，则一定是要使用广度优先遍历各种情况。
介绍代码中的几个变量：
q[i] 做队列使用，用于存储矩阵的不同状态。
f[i] 此数组和q配合起来，用来记录对应位置状态的是由谁变化而来的。
b[i] 记录次状态是由那个状态变化那个位置的数据而来的。

#include<stdio.h>
#include<stdlib.h>
bool mat[4][4];
int q[90000],f[90000],b[90000];
void printMat(int m)
{int mat1[16];for(int i=15;i>=0;i--){mat1[i]=m%2;m=m/2;}for(int i=0;i<16;i++){printf("%d ",mat1[i]);if((i+1)%4==0) putchar(10);}
}
int main()
{int r=-1,h=0,k=-1;q[h]=0;for(int i=0;i<4;i++){for(int j=0;j<4;j++){char c;scanf("%c",&c);if(c=='+')mat[i][j]=false;        else mat[i][j]=true;q[h]=(q[h]<<1)+mat[i][j]; }getchar();}h++;f[0]=-1;b[0]=0;while(r<h){r++;if(q[r]==65535){k=r;break;                 }if(h>=90000) continue;for(int i=b[r]+1;i<=16;i++){b[h]=i;f[h]=r;q[h]=q[r];q[h]^=1<<(16-i);int l = (i-1)%4;int r = (i-1)/4;for(int j=0;j<4;j++){int x = j+r*4+1;  //行 int y = j*4+l+1;q[h]^=1<<(16-x);q[h]^=1<<(16-y);}h++;}}if(k>=0){int step[20];int w=0;while(f[k]!=-1){step[w]=b[k];k=f[k];w++;}printf("%d\n",w);while(w--){int r = (step[w]-1)/4+1;int l = (step[w]-1)%4+1;printf("%d %d\n",r,l);}}system("pause");return 0;  
}

这篇关于poj2965_refrigerator(BFS+枚举)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---