导读 ^ _ ^

搜索问题本质是递归问题。
在递归的过程中，进行决策选择。
今天讲解一下飞行员兄弟这道简单深搜题。

飞行员兄弟

算法思路

看到这个问题，数据范围这么小，毫无疑问，用递归暴力搜索。
从上往下，从左往右，对于每个格子，要么动，要么不动。
棘手问题，要保留步骤，那么可以在更新最小值的时候，进行一个备份。

代码实现

#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;
}