4 条题解

  • 1
    @ 2026-9-4 16:44:39
    using namespace std;
    
    const int MAXN = 20;
    
    int n, m;
    int maze[MAXN][MAXN];
    bool visited[MAXN][MAXN];
    int sx, sy, ex, ey;
    
    // 方向顺序:左、上、右、下
    int dx[] = {0, -1, 0, 1};
    int dy[] = {-1, 0, 1, 0};
    
    // 路径存储
    int pathX[MAXN * MAXN];
    int pathY[MAXN * MAXN];
    int pathLen;
    bool found;
    
    void dfs(int x, int y) {
        // 到达终点
        if (x == ex && y == ey) {
            found = true;
            for (int i = 0; i < pathLen; i++) {
                if (i > 0) cout << "->";
                cout << "(" << pathX[i] << "," << pathY[i] << ")";
            }
            cout << endl;
            return;
        }
    
        // 按 左、上、右、下 顺序拓展
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            // 边界检查
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            // 可走且未访问
            if (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;
        cin >> ex >> ey;
    
        // 初始化
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                visited[i][j] = false;
    
        found = false;
        pathLen = 0;
    
        // 起点加入路径
        visited[sx][sy] = true;
        pathX[pathLen] = sx;
        pathY[pathLen] = sy;
        pathLen++;
    
        dfs(sx, sy);
    
        if (!found) {
            cout << -1 << endl;
        }
    
        return 0;
    }
    
    
    

    信息

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