题解 | 迷宫问题

#include <stdio.h>

int main(void) {
    int h, w;
    scanf("%d%d", &h, &w);

    char ch[105][105];
    for (int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            scanf(" %c", &ch[i][j]);
        
    int front = 0, rear = 0;
    int vis[105][105] = { 0 };
    vis[0][0] = 1;
    int qx[105*105], qy[105*105];
    qx[rear] = 0, qy[rear] = 0;
    rear++;

    int path_x[105][105], path_y[105][105];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            path_x[i][j] = -1;
            path_y[i][j] = -1;
        }
    }

    int found = 0;
    while (front < rear && !found) {
        int x = qx[front];
        int y = qy[front];
        front++;

        if(x == h-1 && y == w-1){
            found = 1;
            break;
        }

        int dx[4] = {-1, 0, 0, 1};
        int dy[4] = {0, -1, 1, 0};
        for (int i = 0; i < 4; i++) {
            int cur_x = x + dx[i];
            int cur_y = y + dy[i];
            if (cur_x >= 0 && cur_x < h && cur_y >= 0 && cur_y < w) {
                if (ch[cur_x][cur_y] == '0' && !vis[cur_x][cur_y]) {
                    vis[cur_x][cur_y] = 1;
                    path_x[cur_x][cur_y] = x;
                    path_y[cur_x][cur_y] = y;
                    qx[rear] = cur_x;
                    qy[rear] = cur_y;
                    rear++;
                }
            }
        }
    }
    int ans_x[105*105], ans_y[105*105];
    int count = 0;
    int cur_x = h - 1, cur_y = w - 1;
    while(cur_x != -1 && cur_y != -1){
        ans_x[count] = cur_x;
        ans_y[count] = cur_y;
        count++;
        int px = path_x[cur_x][cur_y];
        int py = path_y[cur_x][cur_y];
        cur_x = px, cur_y = py;
    }
    for(int i = count - 1; i >= 0; i--)
        printf("(%d,%d)\n", ans_x[i], ans_y[i]);
    return 0;
}