返回题解分享
讨论 / 题解分享/ 帖子详情

走迷宫输出路径 - 题解

#include <iostream>
using namespace std;

int a[20][20];
int n, m, qx, qy, zx, zy;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

int rec[410][2];
int cnt = 0;

void dfs(int x, int y, int k) {
    rec[k][0] = x;
    rec[k][1] = y;

    if (x == zx && y == zy) {
        cnt++;
        for (int i = 1; i < k; i++) {
            printf("(%d,%d)->", rec[i][0], rec[i][1]);
        }
        printf("(%d,%d)", rec[k][0],rec[k][1]);
        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 && a[nx][ny] == 1) {
            a[nx][ny] = 0;
            dfs(nx, ny, k + 1);
            a[nx][ny] = 1;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cin >> qx >> qy;
    cin >> zx >> zy;

    a[qx][qy] = 0;
    dfs(qx, qy, 1);

    if (cnt == 0) return -1;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!