走一个大整数迷宫

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>
//关键核心：只有找到更短时间的才继续
// 为什么这样设计：
// 因为对于路径搜索来说，重要的不是计数器的实际值，而是：

// 位置 (x, y)

// 计数器模(p-1)的值（因为最终条件是 counter % (p-1) == 0）

// 如果两个路径：

// 路径A：在时间t₁到达(x,y)，counter_mod = k

// 路径B：在时间t₂到达(x,y)，counter_mod = k

// 且 t₁ < t₂，那么路径A更优，我们只需要记录路径A。
typedef struct {
    int x;
    int y;
    int time;
    int counter;
} pos;

#define N 1000000
pos queue[N];
int queue_front = 0;
int queue_rear = 0;

void queue_push(pos temp) {
    if((queue_rear + 1) % N != queue_front) {
        queue[queue_rear] = temp;
        queue_rear = (queue_rear + 1) % N;
    }
}

bool is_empty_queue() {
    return queue_front == queue_rear;
}

pos queue_pop() {
    if(!is_empty_queue()) {
        pos temp = queue[queue_front];
        queue_front = (queue_front + 1) % N;
        return temp;
    }
    pos temp = {-1, -1, -1, -1};
    return temp;
}

int main() {
    int n, m, p;
    scanf("%d %d %d", &n, &m, &p);
    int a[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    int b[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &b[i][j]);
        }
    }

    // 关键修改：使用最小时间数组代替visited
    int min_time[n][m][p];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < p; k++) {
                min_time[i][j][k] = INT_MAX;
            }
        }
    }

    pos start = {0, 0, 0, a[0][0]};
    int start_mod = a[0][0] % (p-1);
    queue_push(start);
    min_time[0][0][start_mod] = 0;

    int result = -1;
    
    while (!is_empty_queue()) {
        pos temp = queue_pop();
        
        // 如果当前时间大于已知最小时间，跳过
        if (temp.time > min_time[temp.x][temp.y][temp.counter % (p-1)]) {
            continue;
        }
        
        if (temp.x == n-1 && temp.y == m-1) {
            if (temp.counter % (p-1) == 0) {
                // 关键：找到解立即返回，因为BFS第一次找到的就是最短的
                printf("%d", temp.time);
                return 0;
            }
        }

        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        for (int i = 0; i < 4; i++) {
            int nx = temp.x + dx[i];
            int ny = temp.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                int new_counter = temp.counter + a[nx][ny];
                int counter_mod = new_counter % (p-1);
                int new_time = temp.time + 1;
                
                // 只有找到更短时间才继续
                if (new_time < min_time[nx][ny][counter_mod]) {
                    min_time[nx][ny][counter_mod] = new_time;
                    pos t = {
                        .x = nx,
                        .y = ny,
                        .time = new_time,
                        .counter = new_counter
                    };
                    queue_push(t);
                }
            }
        }
    }

    printf("-1");
    return 0;
}