7 solutions

  • 1
    @ 2024-3-26 19:28:55
    #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
    877
    Accepted
    162
    Uploaded By