本文主要是介绍NC14572走出迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这应该是一道入门级的题目了，用bfs和dfs都行
先写一下bfs
一开始本来想省点事，不写结构体了，坐标（i,j）直接用tmp=i*n+j代替，然后x=tmp/n,y=tmp%n，结果忘了j可能会大于等于n,debug一晚上
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 5e2 + 2;char map[maxn][maxn];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int dis[maxn][maxn];
int n, m, startx, starty, endx, endy;
struct node {int x, y;
};bool inmap(int x, int y) {if (x < 1 || x > n) return 0;if (y < 1 || y > m) return 0;return 1;
}int main() {while (cin >> n >> m) {queue<node> q;memset(dis, -1, sizeof(dis));for (int i = 1;i <= n;i++) {for (int j = 1;j <= m;j++) {cin >> map[i][j];if (map[i][j] == 'S') { startx = i; starty = j; }if (map[i][j] == 'E') { endx = i; endy = j; }}}q.push({ startx,starty });dis[startx][starty] = 0;while (!q.empty()) {node tmp = q.front(); q.pop();for (int i = 0;i < 4;i++) {int tx = tmp.x + dir[i][0];int ty = tmp.y + dir[i][1];if (inmap(tx, ty) && dis[tx][ty] == -1 && map[tx][ty] != '#') {q.push({ tx,ty });dis[tx][ty] = dis[tmp.x][tmp.y] + 1;}}}if (dis[endx][endy] == -1) cout << "No" << endl;else cout << "Yes" << endl;}return 0;
}
下面是dfs写法：
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 509;int n, m, startx, starty;
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
bool vis[maxn][maxn];
char map[maxn][maxn];
bool flag;bool inmap(int x, int y) {if (x<1 || x>n) return 0;if (y<1 || y>m) return 0;return 1;
}void dfs(int x, int y) {if (map[x][y] == 'E') flag = 1;for (int i = 0; i < 4; i++) {int tx = x + dir[i][0];int ty = y + dir[i][1];if (inmap(tx, ty) && !vis[tx][ty] && map[tx][ty] != '#') {vis[tx][ty] = 1;dfs(tx, ty);}}
}int main() {while (cin >> n >> m) {flag = 0;memset(vis, 0, sizeof(vis));for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> map[i][j];if (map[i][j] == 'S') {startx = i; starty = j;}}}vis[startx][starty] = 1;dfs(startx, starty);if (flag) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}
另外，出现了一个非常奇怪的事情
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 5e2 + 2;int n, m, startx, starty;
char map[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
bool flag;bool inmap(int x, int y) {if (x < 1 || x > n) return 0;if (y < 1 || y > m) return 0;return 1;
}
下面两个dfs是一样的
/*void dfs(int x, int y) { //这个是错的if (map[x][y] == 'E') flag = 1;for (int i = 0; i < 4; i++) {int tx = x + dir[i][0];int ty = y + dir[i][1];if (inmap(tx, ty) && !vis[tx][ty] && map[ty][ty] != '#') {vis[tx][ty] = 1;dfs(tx, ty);}}
}*/void dfs(int x, int y) { //这个是对的if (map[x][y] == 'E') flag = 1;for (int i = 0; i < 4; i++) {int tx = x + dir[i][0];int ty = y + dir[i][1];if (inmap(tx, ty) && !vis[tx][ty] && map[tx][ty] != '#') {vis[tx][ty] = 1;dfs(tx, ty);}}
}int main() {while (cin >> n >> m) {flag = 0;memset(vis, 0, sizeof(vis));for (int i = 1;i <= n;i++) {for (int j = 1;j <= m;j++) {cin >> map[i][j];if (map[i][j] == 'S') { startx = i; starty = j;}}}vis[startx][starty] = 1;dfs(startx, starty);if (flag) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}这篇关于NC14572走出迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
