Flip Game
这个题目数据量只有4*4 所以进行深度优先搜索完成所有情况的遍历,求出最短步数就可以了。
这个题目有一个需要注意的地方就是在读入数据的时候要用getchar()进行读取回车。这个操作在读取字符的时候一定是要注意的。
在读取整形变量的时候是不需要的。
建立一个int map[6][6];型的整形数组,在读入字符的时候是黑丝b就初始化为1,是白色就初始化为0
每一个棋子都有翻与不翻两种状况,分别沿着这两种情况深度搜索下去就行了。
在每一次搜索之前进行判定 是否是已经全黑或者说全白 通过将所有的数组数加在一起
如果出现了sum%16==0 就说明已经成功了。在在翻转的时候 要注意翻转的棋子是否在数组内。
在每一次翻转成功之后就比较步数,步数少的作为结果,如果出现了到最后步数还是初始时的33的时候输出impossible
#include<cstdio> #include<iostream> using namespace std; int map[6][6]; int i,j,step=0,c = 33; char s; int check(int map[][6]) { int sum =0; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) sum = sum + map[i][j]; if(sum%16==0) return 1; else return 0; } void turn(int row,int col) { map[row+1][col] = !map[row+1][col]; map[row][col] = !map[row][col]; map[row-1][col] = !map[row-1][col]; map[row][col+1] = !map[row][col+1]; map[row][col-1] = !map[row][col-1]; } void dfs(int row,int col,int step) { if(check(map)) { if(c>step) c=step; return; } if(col>5||col<1||row>4||row<1) return ; if(col>4) { row+=1; col =1; } turn(row,col); dfs(row,col+1,step+1); turn(row,col); dfs(row,col+1,step); } int main() { //freopen("1.txt","r",stdin); for(i=1;i<=4;i++) { for(j=1;j<=4;j++) { scanf("%c",&s); if(s=='b') map[i][j]=1; else map[i][j]=0; } getchar(); } dfs(1,1,step); if(c == 33) printf("Impossible\n"); else printf("%d\n",c); return 0; }