C++U5-第02课-深度优先搜索2

学习目标

 迷宫地图类的深搜

 对于二维数组中一个点的行和列x,y;与周围8个方向位置的关系

[迷宫的相邻点]

遍历 (x,y) 的周围的四个方向，判断是否越界，无越界输出。

【参考代码】
#include <iostream>
using namespace std;

int n, m, x, y;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

bool check(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main() {
    cin >> n >> m >> x >> y;
    for(int i = 0; i < 4; i++){
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(check(nx,ny)) cout << nx << " " << ny << endl;
        else cout << "NA" << endl; 
    }
    return 0;
}

一般表示地图可以用整型数组1、0  或字符数组中的字符

[迷宫之判定]

 重点思路

【算法分析】
dfs，不回溯，如果下一个点符合条件则继续递归，直到找到终点。

vis[][] //vis[x][y]标记点(x,y)是否已访问
DFS(int x, int y)  //当前正在访问的点是(x,y)
    if (x, y) 是终点 //边界
       走到终点
       return    //返回
    vis[x][y] = true  //标记点(x,y)已访问
    for 点(x, y)的上下左右点(nx,ny)
        if(nx,ny)没越界&&(nx,ny)未访问&&(nx,ny)不是墙
            DFS(nx,ny)  //递归访问点(nx,ny)

【参考代码】
#include <iostream>
using namespace std;

const int N = 50;
int n, m;
int mp[N][N];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  
bool vis[N][N], flag;         //vis[x][y] 标记点(x,y)是否已访问

bool check(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void dfs(int x, int y){      //当前正在访问的点是(x,y)
    if(x == n && y == m){  //边界
        flag = true;
        return;
    }
    vis[x][y] = true;      //标记点(x,y)已访问
    for(int i = 0; i < 4; i++){
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(check(nx, ny) && !vis[nx][ny] && !mp[nx][ny]){
            dfs(nx,ny);    //递归访问点(nx,ny) 
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> mp[i][j];    
        }
    }
    dfs(1,1);
    if(flag) cout << "YES";
    else cout << "NO";
    return 0;
}

[迷宫之方案数]（回溯知识）

回溯指的是状态重置，可以理解为回到过去,恢复现场是在编码的过程中，是为了节约空间而使用的一种技巧，而回溯算法其实是深度优先遍历特有的一种现象。之所以是深度优先遍历，是因为我们要解决的问题通常是在一颗树上完成的，在这颗树上搜索需要的答案，一般使用深度优先遍历

【算法分析】
每到一次终点，说明找到一种新方案。
到达终点后，不要停止，回头继续找其他路。
不会完全重复，因为走过的地方被标记了。

【参考代码】
#include <iostream>
using namespace std;

const int N = 15;
int n, m, sx, sy, fx, fy, t, cnt;
int mp[N][N];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  
bool vis[N][N];         //vis[x][y] 标记点(x,y)是否已访问

bool check(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void dfs(int x, int y){      // 当前位置 (x, y) 
    if(x == fx && y == fy){ // 边界：终点  
        cnt++;                // 方案数加 1
        return;
    }
    vis[x][y] = true;      // 标记已经走过 
    for(int i = 0; i < 4; i++){
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        // 没有越界 && 没有访问 && 不是障碍物
        if(check(nx,ny) && !vis[nx][ny] && mp[nx][ny] != 1){
            dfs(nx, ny);
        }
    }
    vis[x][y] = false;  //回溯 
}

int main() {
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;
    for(int i = 1; i <= t; i++){
        int x, y;
        cin >> x >> y;
        mp[x][y] = 1;
    }
    dfs(sx,sy);
    cout << cnt;
    return 0;
}

初赛知识：

"应用软件是为满足特定用户需求而设计和开发的程序，用于完成各种任务和活动。" 应用软件是指在计算机上运行的具体应用程序，旨在满足用户的特定需求，并提供各种功能和服务，例如办公软件、游戏、媒体播放器等。应用软件是根据用户需求进行开发和设计的，以便满足用户在各种任务和活动中的要求。

[迷宫之最少花费时间]

【算法分析】
dfs，回溯，如果下一个点符合条件则继续递归，直到找到终点。

mp[][]  //迷宫
vis[][] //vis[x][y]标记点(x,y)是否已访问
DFS(int x, int y, int sum)  //当前正在访问的点是(x,y)
    if (x, y) 是终点 //边界
       走到终点 更新最短时间ans
       return    //返回
    vis[x][y] = true  //标记点(x,y)已访问
    for 点(x, y)的上下左右点(nx,ny)
        if(nx,ny)没越界&&(nx,ny)未访问&&(nx,ny)不是墙
            if 是怪兽
            DFS(nx,ny,sum + (mp[nx][ny] - '0') + 1)  //需要花费 1 分钟 + 消灭怪兽的时间 
            else 
            DFS(nx, ny, sum + 1);  // 空地需要花费 1 分钟
    回溯
【参考代码】
#include <iostream>
using namespace std;

const int N = 30;
char mp[N][N];  // 迷宫
int n, m, ans = 2e9;  // 行，列，最短时间 
int sx, sy, ex, ey;  // (sx, sy) 起点，(ex, ey) 终点 
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 方向数组
bool vis[N][N];  // 标记数组 

bool in(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

// 搜索所有可能路径，并维护一个最短时间 
void DFS(int x, int y, int sum) {  // 正在访问 (x, y)，所花时间为 sum 
    if(x == ex && y == ey) {  // 走到终点 
        if(sum < ans) ans = sum;  // 更新最短时间
        return;  // 到达递归边界，返回 
    }
    vis[x][y] = true;
    for(int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        // 未越界 && 未访问 && 不是障碍物和墙 
        if(in(nx, ny) && !vis[nx][ny] && mp[nx][ny] != '#') {
            if(mp[nx][ny] >= '1' && mp[nx][ny] <= '9')
                DFS(nx, ny, sum + (mp[nx][ny] - '0') + 1);  // 需要花费 1 分钟 + 消灭怪兽的时间 
            else
                DFS(nx, ny, sum + 1);  // 空地需要花费 1 分钟
        }
    }
    vis[x][y] = false;  // 回溯 
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if(mp[i][j] == 'Z') sx = i, sy = j;  // 起点位置
            if(mp[i][j] == 'W') ex = i, ey = j;  // 终点位置 
        }
    }
    DFS(sx, sy, 0);  // 从起点出发，找到到达终点的最短时间（也有可能找不到）
    if(ans == 2e9) cout << "IMPOSSIBLE";  // 从起点无法到达终点
    else cout << ans; 
    return 0;
}

本节课作业讲解视频：

稍等，正在整理中···