7 solutions

  • 1
    @ 2024-3-27 11:06:37
    #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
    877
    Accepted
    162
    Uploaded By