数据结构与算法学习笔记----DFS

数据结构与算法学习笔记----DFS

@@ author: 明月清了个风

@@ first publish time: 2024.12.4

@@ revised: 2024.12.5 - 加了Acwing 843. n-皇后问题 。

ps⛹感觉DFS的题基本的思想就是递归，但是每题都有不一样的地方，每一题的思路和模拟过程都单独写在每一题里了。

Acwing 842. 排列数字

[原题链接](842. 排列数字 - AcWing题库)

给定一个整数$n$，将数字$1\sim n$排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数$n$。

输出格式

按照字典序输出所有排列方案，每个方案占一行。

数据范围

$1\le n\le 7$,

思路

感觉这里的搜索思路相对简单，用一个path[]数组记录路径，st[]数组记录每个数字的使用状态。

具体的手动模拟一遍应该就懂了，下面代码的注释也比较全面了

代码

#include <iostream>

using namespace std;

const int N = 10;

int path[N];
bool st[N];
int n;


void dfs(int u)   // 参数u表示当前path中已经有了几个数字，
{
    if(u == n) // path中记录了n个数字后，表示排列完成并输出path
    {
        for(int i = 0; i < n; i ++)
            cout << path[i] << ' ';
        cout << endl;
        return ;
    }
    
    for(int i = 1; i <= n; i ++)    // 因为要按字典序，所以每次都是从1开始看
    {
        if(!st[i])    // 看这个数字在这组排列中有没有被使用过
        {
            path[u] = i;    // 没有使用过，那就使用这个数字
            st[i] = true; // 并且将这个数字标记为使用过
            dfs(u + 1);     // 这一轮中使用了一个数字，因此path中多一个数，进一步搜索下一位
            st[i] = false;   // dfs返回后应将刚刚使用过的数字标记为未使用恢复现场。
        }
    }
    
    return ;
}

int main()
{
    cin >> n;
    
    dfs(0);
    
    return 0;
}

Acwing 843. n-皇后问题

[原题链接](843. n-皇后问题 - AcWing题库)

$n$皇后问题是指将$n$个皇后放在$n\times n$de 国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现给定整数$n$，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含一个整数$n$。

输出格式

每个解决方案占$n$行，每行输出一个长度为$n$的字符串，用来表示完整的期盼状态。

其中.表示某一个位置为空，Q表示某一个位置的放个上摆着皇后。

每个方案输出完成后，输出一个空行。

数据范围

$1\le n\le 9$,

思路

⭐️注意点就是对角线和反对角线的判断了，可以将对角线和反对角线看成y = x + a和y = -x + b，对于不同的x和y，两条对角线会映射到不同的截距a和b，下面的代码中加了n是因为对于y - x = a来说，可能会出现算出来的截距小于0，因此要加上一个偏移量，其实如果能自己找到方式，将所有的对角线映射到不同的值就行啦，不一定一定要这样映射。

1. 第一种搜索顺序

   根据题意，每一个格子只有放和不放两种状态，因此可以直接按顺序搜索每种格子的两种情况，最后判断是否满足条件即可，具体的看下面代码吧，注释很多。

   #include <iostream>
   
   using namespace std;
   
   const int N =10;
   
   char g[N][N];
   bool col[N], row[N], dg[N * 2], udg[N * 2];
   int n;
   
   void dfs(int x, int y, int s)  // x, y表示当前枚举的格子，s表示当前放了几个皇后
   {
       if(s > n) return ;   // 放的个数超过了n，直接返回
       if(y == n) y = 0, x ++;  // 列数越界了，进入下一行
       if(x == n)     // 到了最后一行
       {
           if(s == n)  // 满足条件，输出矩阵
           {
               for(int i = 0; i < n; i ++) cout << g[i] << endl;
               cout << endl;
           }
           return;
       }
       
       g[x][y] = '.';   // 这一格子不放，继续搜索
       dfs(x, y + 1, s);
   
       if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])   // 判断这个格子能不能放，能放就放，然后继续搜索
       {
           row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
           g[x][y] = 'Q';
           dfs(x, y + 1, s + 1);
           g[x][y] = '.';   // 搜索回来了，恢复现场，还原到之前的状态
           row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
       }
   
       
   
   }
   
   int main()
   {
       cin >> n;
       
       dfs(0 , 0, 0);
       
       return 0;
   }
   

2. 第二种搜索顺序

   根据题意可以知道，每一行，每一列，每一个斜线都只会有一个皇后，因此，可以直接枚举每一行放在哪，然后判断其他是否成立，这样的顺序会比上面快很多，因为是按行来枚举，代码如下

   #include <iostream>
   #include <cstring>
   
   using namespace std;
   
   const int N = 20;
   
   char g[N][N];
   int n;
   bool col[N], dg[N * 2], udg[N * 2];
   
   
   void dfs(int u)
   {
       if(u == n)
       {
           for(int i = 0; i < n; i ++) puts(g[i]);
           cout << endl;
           
           return ;
       }
   
       for(int i = 0; i < n; i ++)
       {
           if(!col[i] && !dg[u + i] && !udg[n - u + i])
           {
               col[i] = dg[u + i] = udg[n - u + i] = true;
               g[u][i] = 'Q';
               dfs(u + 1);
               g[u][i] = '.';
               col[i] = dg[u + i] = udg[n - u + i] = false;
           }
       }
       
       return ;
   }
   
   int main()
   {
       cin >> n;
       for (int i = 0; i < n; i ++ )
           for (int j = 0; j < n; j ++ )
               g[i][j] = '.';
   
       dfs(0);
       
       return 0;
   }
   
   

原文地址：https://blog.csdn.net/weixin_60278491/article/details/144270067

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！