2 条题解

  • 0
    @ 2026-5-20 20:11:56
    using namespace std;
    
    const int N = 20;
    int n, m;
    int maze[N][N];
    int sx, sy, ex, ey;
    bool visited[N][N];
    int pathX[N * N], pathY[N * N];
    int pathLen;
    bool hasPath = false;
    int dx[4] = {0, -1, 0, 1};
    int dy[4] = {-1, 0, 1, 0};
    
    void dfs(int x, int y) {
        if (x == ex && y == ey) {
            hasPath = true;
            for (int i = 0; i < pathLen; i++) {
                cout << "(" << pathX[i] << "," << pathY[i] << ")";
                if (i != pathLen - 1) {
                    cout << "->";
                }
            }
            cout << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && 
                maze[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                pathX[pathLen] = nx;
                pathY[pathLen] = ny;
                pathLen++;
                dfs(nx, ny);
                pathLen--;
                visited[nx][ny] = false;
            }
        }
    }
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> maze[i][j];
            }
        }
        cin >> sx >> sy >> ex >> ey;
        if (maze[sx][sy] == 0 || maze[ex][ey] == 0) {
            cout << -1 << endl;
            return 0;
        }
        visited[sx][sy] = true;
        pathX[0] = sx;
        pathY[0] = sy;
        pathLen = 1;
        dfs(sx, sy);
        if (!hasPath) {
            cout << -1 << endl;
        }
    }
    
    

    信息

    ID
    1303
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    200
    已通过
    48
    上传者