走一个大整数迷宫

p≡1(modp−1)，所以ci,j=ai,j，b不需要处理

#include <stdio.h> #include <stdbool.h> #include <string.h> #include <limits.h> // 核心设计思想： // 路径搜索的关键状态是 (位置x, 位置y, counter%(p-1)) // 若两条路径到达同一(x,y)且counter模值相同，时间更短的路径更优，长路径可直接舍弃 // 用三维数组min_time记录每个状态的最小时间，替代传统visited数组实现剪枝 // BFS队列节点结构体：存储当前位置、时间、累计counter值 typedef struct { int x; // 当前位置的横坐标 int y; // 当前位置的纵坐标 int time; // 到达当前位置花费的时间 int counter; // 到达当前位置的累计counter值（累加网格a的数值） } pos; #define N 1000000 // 循环队列的最大容量，避免BFS过程中队列溢出 pos queue[N]; // 用数组模拟循环队列，存储BFS节点 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; // n:网格行数 m:网格列数 p:模值参数（要求最终counter%(p-1)==0） // 补全原代码缺失的输入参数 scanf("%d %d %d", &n, &m, &p); int a[n][m]; // 网格a：移动到对应位置时，counter会累加a[x][y]的值 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &a[i][j]); // 补全原代码缺失的取址符 } } // 原代码中b数组未使用，可删除以节省内存 int b[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &b[i][j]); // 补全原代码缺失的取址符 } } // 三维最小时间数组：min_time[x][y][k]表示到达(x,y)且counter%(p-1)=k的最小时间 // 初始化为INT_MAX（无穷大），表示初始状态不可达 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; } } } // 初始化起点状态：起点为(0,0)，初始时间0，counter初始值为a[0][0] pos start = {0, 0, 0, a[0][0]}; // 计算起点counter的模值（核心状态维度之一） int start_mod = a[0][0] % (p-1); queue_push(start); // 起点入队，启动BFS min_time[0][0][start_mod] = 0; // 起点对应状态的最小时间为0 int result = -1; // 结果初始化：-1表示无解 while (!is_empty_queue()) { // 队列非空时持续BFS遍历 pos temp = queue_pop(); // 取出队首节点 // 核心剪枝操作：如果当前时间大于该状态的已知最小时间，直接跳过 // 说明存在更短路径到达同一状态，当前路径无意义 int curr_mod = temp.counter % (p-1); if (temp.time > min_time[temp.x][temp.y][curr_mod]) { continue; } // 终止条件：到达终点(n-1,m-1) 且 满足counter%(p-1)==0的约束 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) { // 计算新状态的counter值：累加新位置的a值 int new_counter = temp.counter + a[nx][ny]; // 计算新状态的模值（核心状态维度） int counter_mod = new_counter % (p-1); int new_time = temp.time + 1; // 移动一步，时间+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); } } } } // 队列遍历完毕仍未找到合法路径，输出-1表示无解 printf("-1"); return 0; } </limits.h></string.h></stdbool.h></stdio.h>

这道题太变态了，没有AI的帮助我基本解不出

#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;
}