BFS做法:
#include<iostream> #include<cstring> #include<queue> using namespace std; typedef pair<int, int> PII; const int N = 505; char map[N][N]; bool st[N][N]; int n, m, flag = 0; int sx, sy, ex, ey; void bfs(int x, int y) { queue<PII>q; q.push({ x, y }); memset(st, 0, sizeof(st)); // 关键是这行, 有这行就100%对 st[x][y] = true; int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, -1, 0, 1 }; while (q.size()) { PII t = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int xx = t.first + dx[i], yy = t.second + dy[i]; if (xx >= 0 && xx < n && yy >= 0 && yy < m && !st[xx][yy] && map[xx][yy] != '#') { // 注意:map[xx][yy]这个地方最好是!=‘#’ q.push({ xx, yy }); st[xx][yy] = true; // cout << "xx = " << xx << "yy = " << yy << endl; if (xx == ex && yy == ey) { flag = 1; return; } } } } } int main() { while (cin >> n >> m) { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { cin >> map[i][j]; if (map[i][j] == 'S') sx = i, sy = j; if (map[i][j] == 'E') ex = i, ey = j; } // cout << "2ex = " << ex << " "<< "2ey = " << ey << endl; bfs(sx, sy); if (flag == 1) cout << "Yes" << endl; else cout << "No" << endl; flag = 0; } return 0; }