导读 ^ _ ^
搜索问题本质是递归问题。
在递归的过程中，进行决策选择。
今天讲解一下飞行员兄弟这道简单深搜题。
飞行员兄弟
算法思路
看到这个问题，数据范围这么小，毫无疑问，用递归暴力搜索。
从上往下，从左往右，对于每个格子，要么动，要么不动。
棘手问题，要保留步骤，那么可以在更新最小值的时候，进行一个备份。
代码实现
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
int N = 0x3f3f3f3f;
char a[6][6];
vector<PII> q;//单层逻辑
vector<PII> q2;//备份
//检查是否到达目标状态
bool check( ) {
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
if (a[i][j] != '-') return false;
return true;
}
//改变状态
void change(int x,int y) {
if (a[x][y] == '-') a[x][y] = '+';
else a[x][y] = '-';
}
//递归搜索
void dfs(int x, int y, int count)
{
if( y == 5) x = x + 1,y = 1; //注意，行到这里才会动一下
if(check()) {
N = min(N,count);
if(N == count) q2 = q;
return;
}
if( x == 5) return;
if (count >= N) return;
//动
for(int i = 1; i <= 4; i++)
change(i,y),change(x,i);
change(x,y);
q.push_back({x,y});
dfs(x, y+1,count + 1);
q.pop_back( );//回溯
//不动
for(int i = 1; i <= 4; i++)
change(i,y),change(x,i);
change(x,y);
dfs(x, y+1,count);
}
int main( )
{
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
cin >> a[i][j]; //空格不会读
dfs(1,1,0);
printf("%d\n",N);
for(auto item : q2) //输出步骤
printf ("%d %d\n",item.first,item.second);
return 0;
}