3.搜索与图论

第一章 DFS

1.1 排列数字

思路:

什么是DFS?(以及两个重要思想)
DFS是一个很执着的人,他不撞南墙不回头,所以他的搜索 ①不会是最短的路径,并且,其需要②回溯 (回到上一状态,且恢复现场),因为他虽然不太聪明,但他要是想到达目的地,当他撞墙后,他还是要回头走到你来的起点,去寻找下一条可能的路径直到他到达目的地
**①不会是最短的路径:**不能用DFS求最短路,BFS可以
②回溯: 就和递归一样,不过在递归前改状态,递归后把状态改回去
为什么递归前要改状态: 为了防止后续的状态回到当前状态,从而死循环
为什么递归后要把状态改回去: 因为每个状态可能多次访问,就像走迷宫一样,到达终点的路有n条,可能他们都要经过点G,要是不该回去,能到终点的n条路—>仅仅只有一条了

做DFS的思路

什么时候用DFS:要是每个过程可以抽象为状态存储就应该可以(个人认为)
1. 怎么把每步抽象为状态
2. flag[]数组记录每个状态是否有使用过(以免死循环)
3. path[]可以记录其从哪个节点来的(一般DFS都会有)[不只一个哟,n皇后问题有好多,dg[],udg[],cols[]]

#include <iostream>

using namespace std;
const int N = 10;
int n, ans[N], memo[N];

/* di为dfs(i)
         d0
      1   2   3  // 第1个位置可选的数字
     /    |    \
    d1   d1    d1     // 进入第2个位置
  2  3   1  3   1  2  // 选过不能再选
 /   |   |  |   |  \
d2  d2   d2 d2  d2 d2  // 进入第3个位置
3   1    3  1   3   1  */
// 时间复杂度:n*n-1*n-2*1=>O(n!)
// 空间复杂度:数组都是N的=>O(n)
void dfs(int index) {  // index为[0,n)索引
    if (index == n) {
        for (int i = 0; i < n; i++) printf("%d ", ans[i]);
        puts("");
    } else {
        for (int num = 1; num <= n; num++) {
            if (memo[num]) continue;
            ans[index] = num, memo[num] = 1;
            dfs(index + 1);
            memo[num] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(0);
    return 0;
}

2026年3月6日21:56:08: 今天的我已经乱杀dfs了,至少玩的比当年透彻多了,如下是2023年9月21日11:22:47写的笔记(知识的诅咒)
1.t为当前状态 ，t+1就是下一个状态咯
2.满足输出条件: 当 当前状态到目标状态了，就是满足条件了
3.这个else中的for循环: 其实就是枚举这个状态的 下一个状态 有哪些，
    * 例如:这题是"全排列"，那下一个状态就有n种(别急着反驳我，看完)
    * 例如:迷宫，对于当前状态来说，四个方向，只要不是墙都可以走(别急着反驳我，看完)
4.满足条件的才是真正的下一个状态:
    * 全排列(例.n=5):1 2 _ 这个位置可以填1~5(n种)，只是1，2填过了，所以真正的下一个状态是3，4，5
        if (!flag[i])
    * 迷宫:可能只对于当前状态来说，可能会出现可以回去的状态，但肯定不行对吧，所以真正的状态是 ***没有走过的***，并且是***合法***的
        if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0 && flag[x][y] == false)
5.为进一步搜索所需要的状态打上标记: 那个愚蠢的小人决定走当前这条路了
6.递归: 他已经开始踏上这条路了
7.恢复到打标记前的状态: 不知道这个愚蠢的小人有没有成功，或许他成功了吧，呃，也有可能碰壁了，**但不管怎么说他回到了这**，回到了开始的地方，他抹去了来过的痕迹， 成功也好，失败也罢，他反正决定重新开始新的旅程，走他的下一条路，

/*        d0          // di为dfs(i)       
      1   2   3       // 第1个位置可选的数字 
     /    |    \                          
    d1   d1    d1     // 进入第2个位置
  2  3   1  3   1  2  // 选过不能再选
 /   |   |  |   |  \
d2  d2   d2 d2  d2 d2  // 进入第3个位置
3   1    3  1   3   1  */
// 时间复杂度:n*n-1*n-2*1=>O(n!)
// 空间复杂度:数组都是N的=>O(n)
const int N = 10;
int n, ans[N], memo[N];

void dfs(int index) {  // index为[0,n)索引
    if (index == n) { for (int i = 0; i < n; i++) printf("%d ", ans[i]); puts(""); }
    else {
        for (int num = 1; num <= n; num++) {
            if (memo[num]) continue;
            ans[index] = num, memo[num] = 1;
            dfs(index + 1);
            memo[num] = 0; // 回溯
        }
    }
}// 调用处: dfs(0)

注意:

要是忘记模板—>看模板版本
要是不知道怎么运用DFS—>看思路–>做DFS的思路
要是不知道DFS是什么—>看解释版本

心得:

2023年9月21日11:22:47

首次编辑时间: 2023年9月21日11:22:47

每日一题:

1.2 n皇后问题

思路:

0  1  2  3    dg: 比如在(0,1)放置Q,那主对角#为1-0=2-1=3-2=1;
0    Q        udg:副对角〇为1+0=0+1=1
1 〇     #    1°因为dg是做差(可能为负)所以都加n
2          #  2°因为udg是加和(所以N最大可以是(9,9)=>9+9=18)所以N要开到20
3             3°第2行的(2,1) 1-2=-1不会误判吗? 不会因为有col[1],且此后(2,3/4/5..)不可能为负数
!!!不用怕忘,非常好推,你dg 1+0=1,2+1=3,3+2=5,都不一样,所以是作差!
①时间复杂度: 第一行:n个位置,第二行:n-1个位置(排除同列),,,第n-1行:1个位置;=>O(n!)【总体因为还有对角线剪枝,会<<】
②空间复杂度: 标记数组3*n,棋盘n^2,所以O(n^2+n)=>O(n^2)

代码:

解释版本
模板版本

#include <iostream>

using namespace std;
const int N = 20;
int n, col[N], dg[N], udg[N];  // dg为对角↘,udg为副对角
string ans(N* N, '.');         // 最终输出的棋盘

void dfs(int curRow) {
    if (curRow == n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) printf("%c", ans[i * n + j]);
            puts("");
        }
        puts("");
    } else {
        /*
          0  1  2  3
        0    Q
        1 〇     #
        2          #
        3
        dg: 比如在(0,1)放置Q,那主对角#为1-0=2-1=3-2=1;
        udg:副对角〇为1+0=0+1=1
        1°因为dg是做差,可能为负不方便处理索引,所以都加n(小明是第11,全班都加n分,小明还是第11)
          因为udg是加和,所以N最大可以是(9,9)=>9+9=18, 所以N要开到20
        2°第2行的(2,1) 1-2=-1不会误判吗? 不会因为col[1]是记录的,col[],dg[],udg[]共同决定
        3°很好记的,忘了,非常好推,你dg 1+0=1,2+1=3,3+2=5,都不一样,所以是作差!
        */
        for (int c = 0; c < n; c++) {
            int dgIndex = c - curRow + n, udgIndex = c + curRow;
            if (col[c] == 1 || dg[dgIndex] == 1 || udg[udgIndex] == 1) continue;
            col[c] = dg[dgIndex] = udg[udgIndex] = 1;
            ans[curRow * n + c] = 'Q';
            dfs(curRow + 1);
            ans[curRow * n + c] = '.';  // 回溯
            col[c] = dg[dgIndex] = udg[udgIndex] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(0);
    return 0;
}

/*0  1  2  3  dg: 比如在(0,1)放置Q,那主对角#为1-0=2-1=3-2=1;
0    Q        udg:副对角〇为1+0=0+1=1
1 〇     #    1°因为dg是做差(可能为负)所以都加n
2          #  2°因为udg是加和(所以N最大可以是(9,9)=>9+9=18)所以N要开到20
3             3°第2行的(2,1) 1-2=-1不会误判吗? 不会因为有col[1],且此后(2,3/4/5..)不可能为负数
!!!不用怕忘,非常好推,你dg 1+0=1,2+1=3,3+2=5,都不一样,所以是作差!*/
// 时间复杂度: 第一行:n个位置,第二行:n-1个位置(排除同列),,,第n-1行:1个位置;=>O(n!)【总体因为还有对角线剪枝,会<<】
// 空间复杂度: 标记数组3*n,棋盘n^2,所以O(n^2+n)=>O(n^2)

const int N = 20;
int n, col[N], dg[N], udg[N];  // dg为对角↘,udg为副对角
string ans(N* N, '.');         // 最终输出的棋盘

void dfs(int curRow) {
    if (curRow == n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) printf("%c", ans[i * n + j]);
            puts("");
        } puts("");
    } else {
        for (int c = 0; c < n; c++) {
            int dgIndex = c - curRow + n, udgIndex = c + curRow;
            if (col[c] == 1 || dg[dgIndex] == 1 || udg[udgIndex] == 1) continue;
            col[c] = dg[dgIndex] = udg[udgIndex] = 1;
            ans[curRow * n + c] = 'Q';
            dfs(curRow + 1);
            ans[curRow * n + c] = '.';  // 回溯
            col[c] = dg[dgIndex] = udg[udgIndex] = 0;
        }
    }
}// 调用处: dfs(0) // 从第0行开始[0,n)索引

注意:

因为dg是做差(可能为负)所以都加n
因为udg是加和(所以N最大可以是(9,9)=>9+9=18)所以N要开到20

心得:

2023-9-19 16:47:23

首次编辑时间: 2023-9-19 16:47:23

每日一题:

第二章 BFS

2.1 走迷宫

思路:

什么是BFS
1. 按层搜索
2. 当每个状态间的权值都相等时,其搜索为最短结果
3. BFS一般有个dist[]来记录搜索ans,即到达当前状态之前,经历了几个状态
  - 走迷宫: dist[i][j]表示从起点到(i,j)的距离,并且这里每个状态间都是1的权值,所以dist[aim.x][aim.y]就是最后要的从起点–>(aim.x,aim.y)的最短步数
  - 八数码: dist[][]从数组–>哈希,为什么??因为你每个状态不能像走迷宫一样是一个坐标,可以用二维,你的每个状态是string,得用哈希来存这样的状态,和该状态的值,那么最后目标状态的值就是ans
遇到BFS怎么想
1. 找什么是状态,
2. 找怎么表示状态
  - 走迷宫问题: 每个格子是一个状态
  - 八数码问题: 每种矩阵是一个状态
3. 状态怎么转移
4. 别忘标记!!!!!,和DFS一样的
和DFS的不同,这个不用回溯

代码:

解释版本
模板版本

/*
0 1 0 0 0 | 0 # 6 7 8   // 从0开始,#为墙,1~8为遍历到的次序
0 1 0 1 0 | 1 # 5 # 7   // 4方向遍历
0 0 0 0 0 | 2 3 4 5 6   //
0 1 1 1 0 | 3 # # # 7
0 0 0 1 0 | 4 5 6 # 8
*/
#include <iostream>
#include <queue>
#define pii pair<int, int>

using namespace std;
const int N = 110;
int n, m, map[N][N], dist[N][N];  // dist[i][j]表示从(1,1)到(i,j)的最短距离
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int bfs(int sx, int sy) {
    int flag[N][N] = {0};
    queue<pii> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (flag[x][y]) continue;
        flag[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 1 || nextX > n || nextY < 1 || nextY > m) continue;
            if (map[nextX][nextY] == 1 || flag[nextX][nextY]) continue;
            dist[nextX][nextY] = 1 + dist[x][y];
            q.push({nextX, nextY});
        }
    }
    return dist[n][m];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) scanf("%d", &map[i][j]);
    }
    printf("%d", bfs(1, 1));
    return 0;
}

/* // 从0开始,#为墙,1~8为遍历到的次序
0 1 0 0 0 | 0 # 6 7 8   
0 1 0 1 0 | 1 # 5 # 7   
0 0 0 0 0 | 2 3 4 5 6   
0 1 1 1 0 | 3 # # # 7
0 0 0 1 0 | 4 5 6 # 8 */
// 时间复杂度: 每个格子至多入队一次,出队时检测4方向=>4×n×m==>O(n×m)
// 空间复杂度: 二维数组==>O(n×m)

const int N = 110;
int n, m, map[N][N], dist[N][N];  // dist[i][j]表示从(1,1)到(i,j)的最短距离
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int bfs(int sx, int sy) {
    int flag[N][N] = {0}; // 当然BFS熟练后,不刚需flag,dist初始化为-1表示没有走过
    queue<pii> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (flag[x][y]) continue;
        flag[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 1 || nextX > n || nextY < 1 || nextY > m) continue;
            if (map[nextX][nextY] == 1 || flag[nextX][nextY]) continue;
            dist[nextX][nextY] = 1 + dist[x][y];
            q.push({nextX, nextY});
        }
    }
    return dist[n][m]; // 返回(1,1)到(n,m)的最短距离
} // 主函数调用 printf("%d", bfs(1, 1)); // [1,n][1,m]索引

注意:

心得:

2023年9月22日

首次编写日期: 2023年9月22日

每日一题:

2.2 八数码

思路:

这个每个状态都是字符串, 所以用map存储

代码:

解释版本
模板版本

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#define pii pair<int, int>

using namespace std;
const int COL = 3;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string ans = "12345678x";

pii i2p(int index) { return {index / COL, index % COL}; }
int p2i(int x, int y) { return x * COL + y; };

// 索引和坐标的转换关系: x=index/3; y=index%3; index=x*3+y
int bfs(string input) {
    queue<string> q;
    unordered_map<string, int> dist;
    unordered_set<string> isVisited;
    q.push(input);
    while (q.size()) {
        string str = q.front();
        q.pop();
        int xIndex = str.find('x'), x, y;
        tie(x, y) = i2p(xIndex);
        if (isVisited.count(str)) continue;
        isVisited.insert(str);
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= 3 || nextY < 0 || nextY >= 3) continue;
            int nextIndex = p2i(nextX, nextY);
            string nextStr = str;
            swap(nextStr[xIndex], nextStr[nextIndex]);
            if (isVisited.count(nextStr)) continue;
            // printf("%s | %s\n", str.c_str(), nextStr.c_str());
            dist[nextStr] = dist[str] + 1;
            q.push(nextStr);
        }
    }
    return dist.count(ans) ? dist[ans] : -1;
}

int main() {
    string input;
    for (int i = 0; i < 9; i++) {
        char ch;
        cin >> ch;
        input += ch;
    }

    printf("%d", bfs(input));

    return 0;
}

/* 1 2 3   1 2 3   1 2 3   1 2 3
   x 4 6   4 x 6   4 5 6   4 5 6
   7 5 8   7 5 8   7 x 8   7 8 x
123x46758->1234x6758->1234756x8->12347568x */
// 时间复杂度:9位全排列有9!种情况,每种情况4拓展=>O(9!×4)
// 空间复杂度:每个状态9字符=>O(9!×9)
const int COL = 3;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string ans = "12345678x";

pii i2p(int index) { return {index / COL, index % COL}; }
int p2i(int x, int y) { return x * COL + y; };

// 索引和坐标的转换关系: x=index/3; y=index%3; index=x*3+y
int bfs(string input) {
    queue<string> q;
    unordered_map<string, int> dist;
    unordered_set<string> isVisited;
    q.push(input);
    while (q.size()) {
        string str = q.front();
        q.pop();
        int xIndex = str.find('x'), x, y;
        tie(x, y) = i2p(xIndex); // 解构语法
        if (isVisited.count(str)) continue;
        isVisited.insert(str);
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= 3 || nextY < 0 || nextY >= 3) continue;
            int nextIndex = p2i(nextX, nextY);
            string nextStr = str;
            swap(nextStr[xIndex], nextStr[nextIndex]);
            if (isVisited.count(nextStr)) continue;
            // printf("%s | %s\n", str.c_str(), nextStr.c_str());
            dist[nextStr] = dist[str] + 1;
            q.push(nextStr);
        }
    }
    return dist.count(ans) ? dist[ans] : -1;
} //调用处: printf("%d", bfs(input)); // input="23415x768"

注意:

心得:

每日一题:

2.3 岛屿数量

思路:

类似走迷宫, 主函数遍历二维数组, 如果访问过就continue,否则就进入BFS

代码:

解释版本
模板版本

/*
1 0 0 0 0 1 0 1
1 1 0 0 0 0 0 1
1 1 1 0 0 0 0 1
0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1
1 0 0 1 0 0 0 1
BFS
main中: 遍历r*c
bfs中: 尽可能拓展;
visited: 开为全局
*/

#include <iostream>
#include <queue>
#define pii pair<int, int>

using namespace std;
const int N = 1e3 + 10;
int r, c, map[N][N], visited[N][N] = {0};
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

// 从(x,y)开始尽可能拓展1
void bfs(int sx, int sy) {
    queue<pii> q;
    q.push({sx, sy});
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (visited[x][y]) continue;
        visited[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= r || nextY < 0 || nextY >= c) continue;
            if (visited[nextX][nextY] || map[nextX][nextY] == 0) continue;
            q.push({nextX, nextY});
        }
    }
}


int main() {
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    //
    int ans = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (map[i][j] == 1 && visited[i][j] == 0) {
                ans++;
                bfs(i, j);
            }
        }
    }
    printf("%d", ans);

    return 0;
}

/* 6 8  数字为依次遍历到的次序
   1 0 0 0 0 1 0 1 | 1 0 0 0 0 2 0 3  // STEP1:主 函数遍历二维数组,见到陆地1就访问,如果拓展过就continue,否则就进入BFS
   1 1 0 0 0 0 0 1 | 1 1 0 0 0 0 0 3  // STEP2: BFS只能拓展陆地1 (4方向拓展)
   1 1 1 0 0 0 0 1 | 1 1 1 0 0 0 0 3  // STEP3: 几次BFS就是几个陆地
   0 0 0 0 0 0 0 1 | 0 0 0 0 0 0 0 3
   1 0 0 0 1 0 0 1 | 4 0 0 0 5 0 0 3
   1 0 0 1 0 0 0 1 | 4 0 0 6 0 0 0 3 */
// 时间复杂度:每个点至多进入一次,每个点4拓展=>O(4×n×m)=O(n×m)
// 空间复杂度: 二维数组=>O(n×m)
const int N = 310;
int col, row, map[N][N], visited[N][N];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};

void bfs(int sx, int sy) {
    queue<pii> q;
    q.push({sx, sy});
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (visited[x][y]) continue;
        visited[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) continue;
            if (visited[nextX][nextY] || map[nextX][nextY] == 0) continue;
            q.push({nextX, nextY});
        }
    }
}/* 调用处
int lands = 0;
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (map[i][j] == 0 || visited[i][j] == 1) continue;
        lands++;
        bfs(i, j);
    }
}
printf("%d", lands);*/

注意:

心得:

日期

居然能找到这来, 真是厉害~

3.搜索与图论

第一章 DFS

1.1 排列数字

思路:

代码:

注意:

心得:

每日一题:

1.2 n皇后问题

思路:

代码:

注意:

心得:

每日一题:

第二章 BFS

2.1 走迷宫

思路:

代码:

注意:

心得:

每日一题:

2.2 八数码

思路:

代码:

注意:

心得:

每日一题:

2.3 岛屿数量

思路:

代码:

注意:

心得:

每日一题: