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; }
本节课作业讲解视频：
稍等，正在整理中···