7 solutions
-
1
#include<iostream> #include<vector> #include<queue> using namespace std; int n; vector<vector<int>> maze; vector<vector<bool>> visited; struct Position { int x, y; }; int dirX[4] = {0, 1, 0, -1}; int dirY[4] = {1, 0, -1, 0}; bool bfs(int startX, int startY, int endX, int endY) { if (maze[startX][startY] == 1 || maze[endX][endY] == 1) { return false; // 起点或终点不可通行 } queue<Position> q; q.push({startX, startY}); visited[startX][startY] = true; while (!q.empty()) { Position current = q.front(); q.pop(); if (current.x == endX && current.y == endY) { return true; } for (int i = 0; i < 4; i++) { int nextX = current.x + dirX[i]; int nextY = current.y + dirY[i]; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0 && !visited[nextX][nextY]) { visited[nextX][nextY] = true; q.push({nextX, nextY}); } } } return false; } int main() { cin >> n; int startX, startY, endX, endY; 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]; } } cin >> startX >> startY >> endX >> endY; startX--; startY--; endX--; endY--; // 转换为从0开始的索引 if (bfs(startX, startY, endX, endY)) { cout << "YES" << endl; } else { cout << "NO" << endl; } }
Information
- ID
- 767
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 8
- Tags
- # Submissions
- 922
- Accepted
- 163
- Uploaded By