7 solutions
-
1
#include <iostream> #include <vector> using namespace std; int n; // 迷宫的规模 vector<vector<int>> maze; // 迷宫矩阵 vector<vector<bool>> visited; // 访问状态记录 // 四个方向移动的坐标变化:上、下、左、右 int dirX[4] = {-1, 1, 0, 0}; int dirY[4] = {0, 0, -1, 1}; bool isValid(int x, int y) { if (x < 0 || y < 0 || x >= n || y >= n) return false; // 越界检查 if (maze[x][y] == 1) return false; // 墙壁检查 if (visited[x][y]) return false; // 已访问检查 return true; } bool dfs(int x, int y, int er, int el) { if (!isValid(x, y)) return false; if (x == er && y == el) return true; // 到达终点 visited[x][y] = true; // 标记当前位置已访问 for (int i = 0; i < 4; i++) { // 尝试四个方向 int nextX = x + dirX[i]; int nextY = y + dirY[i]; if (dfs(nextX, nextY, er, el)) { return true; // 找到一条路径 } } return false; } int main() { cin >> n; maze.resize(n, vector<int>(n)); // 根据迷宫规模初始化迷宫矩阵 visited.resize(n, vector<bool>(n, false)); // 初始化访问状态记录 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> maze[i][j]; } } int sr, sl, er, el; cin >> sr >> sl >> er >> el; sr--; sl--; er--; el--; // 转换为以0为起始的索引 if (maze[sr][sl] == 1 || maze[er][el] == 1) { cout << "NO" << endl; } else if (dfs(sr, sl, er, el)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }
Information
- ID
- 767
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 8
- Tags
- # Submissions
- 922
- Accepted
- 163
- Uploaded By