这两道题类似，前者翻转上下左右相邻的棋子，使得棋子同为黑或者同为白。后者翻转同行同列的所有开关，使得开关全被打开。
题意：有一4x4棋盘，上面有16枚双面棋子（一面为黑，一面为白）， 当翻动一只棋子时，该棋子上下左右相邻的棋子也会同时翻面。以b代表黑面，w代表白面，给出一个棋盘状态， 问从该棋盘状态开始，使棋盘变成全黑或全白，至少需要翻转多少步
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int mp[5][5];
int step,flag;
int range()//遍历整个棋盘是否“清一色”
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(mp[i][j]!=mp[0][0])
return 0;
return 1;
}
void turn(int i,int j)//翻转（i,j）棋子，以及（i,j）周围的棋子
{
mp[i][j]=!mp[i][j];
if(i>0) mp[i-1][j]=!mp[i-1][j];
if(i<3) mp[i+1][j]=!mp[i+1][j];
if(j>0) mp[i][j-1]=!mp[i][j-1];
if(j<3) mp[i][j+1]=!mp[i][j+1];
}
int dfs(int i,int j,int k)
{
if(k==step){
flag = range();
return 0;
}
if(flag||i==4){
return 1;
}
turn(i,j);
if(j<3) dfs(i,j+1,k+1);//一行当中的所有列
else dfs(i+1,0,k+1);//下一行
turn(i,j);//回溯，翻回来
if(j<3) dfs(i,j+1,k);//下一个棋子继续dfs
else dfs(i+1,0,k);
return 0;
}
int main()
{
char str[5][5];
for(int i=0;i<4;i++)
cin>>str[i];
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(str[i][j]=='b') mp[i][j]=1;
else mp[i][j]=0;
for(step=0;step<=16;step++)
{
flag = 0;
dfs(0,0,0);//（x,y）,step
if(flag) break;
}
if(flag) printf("%d\n",step);
else printf("Impossible\n");
return 0;
}一个冰箱上有4*4共16个开关，改变任意一个开关的状态（即开变成关，关变成开）时，此开关的同一行、同一列所有的开关都会自动改变状态。要想打开冰箱，要所有开关全部打开才行。
输入：一个4×4的矩阵，+表示关闭，-表示打开；
输出：使冰箱打开所需要执行的最少操作次数，以及所操作的开关坐标。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = 0x3f3f3f3f;
int mp[5][5];
char str[5][5];
int tx[20],ty[20],ansX[20],ansY[20],ans;
int range()//判断是否“清一色”
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(mp[i][j]==1)
return 0;
return 1;
}
void turn(int x,int y)//翻转同（i,j）同行同列的开关
{
for(int i=0;i<4;i++)
{
mp[x][i]=!mp[x][i];
mp[i][y]=!mp[i][y];
}
mp[x][y]=!mp[x][y];
}
void dfs(int x,int y,int step)
{
int check = range();
if(check==1){ //开关全打开（为0）
if(step<ans){
ans = step;
for(int i=0;i<step;i++){
ansX[i]=tx[i];
ansY[i]=ty[i];
}
}
return;
}
if(x>3||step>16) return;
turn(x,y);
tx[step]=x; ty[step]=y;
if(y<3) dfs(x,y+1,step+1);
else dfs(x+1,0,step+1);
turn(x,y);//回溯，翻回来
if(y<3) dfs(x,y+1,step);
else dfs(x+1,0,step);
return ;
}
int main()
{
for(int i=0;i<4;i++)
cin>>str[i];
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(str[i][j]=='+') mp[i][j]=1;
else mp[i][j]=0;
ans = Max;
dfs(0,0,0);//(x,y),step
cout<<ans<<endl;
for(int i=0;i<ans;i++)
printf("%d %d\n",ansX[i]+1,ansY[i]+1);
return 0;
}
递归的题总是要把人绕进去，特别是回溯那个地方。第二题还可以用其他的解法，解法很多，代码简单，但是数学不过关，看不懂，下次再看看。