算法学习之路|翻转棋

4*4的翻转棋（翻一个棋子的颜色会同时反转上下左右的棋子颜色），给一个棋盘状况，求把所有棋子翻成同色最少需要翻多少次
输入格式：输入4*4的棋盘，b’代表黑，w代表白

输出格式：输出一个数字，表示最少翻多少次，没有解就输出Impossable

输入样例：
bwwb
bbwb
bwwb
bwww

输出样例：
4
解题思路：经典的搜索题，深搜即可。
刚学搜索时写过，但没有ac，重写一次

#include  
#include
#include
using namespace std;  
int chess[4][4];  
int c=33;  
void build()
{  char c;  int i,j;  for(i=0;i<4;i++)  for(j=0;j<4;j++)  {  cin>>c;if(c=='w')  chess[i][j]=0;  else  chess[i][j]=1;  }  
}  
void turn(int x,int y) 
{  if(x>=0&&x<=3&&y>=0&&y<=3)  chess[x][y]=!chess[x][y];  
}  
void flip(int s)
{  int i=s/4; int j=s%4;turn(i,j);  turn(i+1,j);  turn(i,j+1);  turn(i-1,j);  turn(i,j-1);  
}  
int judge()
{  int i,j,s1=0;  for(i=0;i<4;i++)  for(j=0;j<4;j++)  s1+=chess[i][j];  if(s1%16)  return 0;  else  return 1;  
}  
void dfs(int s,int b)
{  if(judge()) {  if(c>b)  c=b;  return;  }  if(s>=16)return;  dfs(s+1,b);  flip(s);  dfs(s+1,b+1);  flip(s);  
}  
int main()  
{  build();dfs(0,0);  if(c==33)printf("Impossible\n");  else  printf("%d\n",c);  return 0;  
}  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！