【报资讯】【DFS】飞行员兄弟

2023-02-13 20:10:05 来源：博客园

(相关资料图)

导读 ^ _ ^

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

飞行员兄弟

算法思路

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

代码实现

#include#include#includeusing namespace std;typedef pair PII;int N = 0x3f3f3f3f;char a[6][6];vector q;//单层逻辑vector 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;}

#谢谢你的观看！

^ _ ^

关键词：讲解一下毫无疑问这个问题