题解 | 走一个大整数迷宫

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

//定义状态结构体
struct state{
    int i, j, counter;
};

int main() {
    //标准竞赛输入输出优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //辅助数组
    int fi[4] = {1, -1, 0, 0};
    int fj[4] = {0, 0, 1, -1};

    //输入数据
    int n, m, p;
    cin >> n >> m >> p;
    int a[n + 1][m + 1];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    int mod = p - 1;
    //三维状态数组，记录达到此状态的用时,初始化为-1
    vector<vector<vector<int>>> dist(n + 1, vector(m + 1, vector(mod, -1)));
    //bfs
    queue<state> q;
    q.push({1, 1,(a[1][1]) % mod});
    dist[1][1][(a[1][1]) % mod] = 0;
    while(!q.empty()){
        //终止条件
        if(dist[n][m][0] != -1){
            break;
        }
        state current = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            if(current.i + fi[i] >= 1 && current.i + fi[i] <= n && current.j + fj[i] >= 1 && current.j + fj[i] <= m && dist[current.i + fi[i]][current.j + fj[i]][(current.counter + a[current.i + fi[i]][current.j + fj[i]]) % mod] == -1){
                q.push({current.i + fi[i],current.j + fj[i],(current.counter + a[current.i + fi[i]][current.j + fj[i]]) % mod});
                dist[current.i + fi[i]][current.j + fj[i]][(current.counter + a[current.i + fi[i]][current.j + fj[i]]) % mod] = dist[current.i][current.j][current.counter] + 1;
            }
        }
    }

    //输出结果
    cout << dist[n][m][0] << '\n';
    
    return 0;
}
// 64 位输出请用 printf("%lld")