给定一个n行m列的迷宫,有些格子可以走,有些有障碍物不能到达。每步可以走到周围8个方向的格子中。请你判断,是否能从左上角走到右下角。如果能走到输出YES,否则输出NO。
时间: 2024-02-25 22:53:40 浏览: 18
好的,这是一个典型的图论问题。您可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法解决。
首先,我们需要将迷宫转换成一个图。可以将迷宫中的每个相邻的可到达的格子都看作一个节点,这些节点之间存在一条边。然后,从左上角的节点开始,使用DFS或BFS算法搜索图,看是否能够到达右下角的节点。
如果能够到达右下角的节点,则输出YES,否则输出NO。
以下是使用DFS算法解决该问题的示例代码(假设迷宫已经存储在一个n行m列的二维数组maze中):
```
bool dfs(int x, int y, int n, int m, vector<vector<bool>>& visited, vector<vector<int>>& maze) {
// 如果当前位置是右下角的节点,则返回true
if (x == n - 1 && y == m - 1) {
return true;
}
// 标记当前位置已经被访问过
visited[x][y] = true;
// 搜索相邻的可到达的格子
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue; // 如果越界了,则忽略该格子
}
if (visited[nx][ny]) {
continue; // 如果已经访问过了,则忽略该格子
}
if (maze[nx][ny] == 0) {
continue; // 如果该格子是障碍物,则忽略该格子
}
if (dfs(nx, ny, n, m, visited, maze)) {
return true; // 如果搜索到了右下角的节点,则返回true
}
}
return false; // 如果搜索完相邻的所有可到达的格子都没有找到右下角的节点,则返回false
}
string canReachEnd(int n, int m, vector<vector<int>>& maze) {
// 初始化visited数组
vector<vector<bool>> visited(n, vector<bool>(m, false));
// 从左上角的节点开始搜索
if (dfs(0, 0, n, m, visited, maze)) {
return "YES";
} else {
return "NO";
}
}
```