题解 | 走一个大整数迷宫

#include <iostream>
#include <vector>
#include <cmath>
#include <deque>
using namespace std;

// (a+b)%m = (a%m + b%m)%m
// (a*b)%m == ((a%m)*(b%m))%m
// 令 a=m+p,b=m+q
// ab = m^2 + m(p+q) + pq
// (ab)%m = (m^2 + m(p+q) + pq)%m = (pq)%m
// (P^n)%(p-1) = (p%(p-1)*p%(p-1)*...)%(p-1) = 1

// 3维bsf参考网友的示例，c的值在0~p-2之间，x,y,c确定的情况下，四方向的c也是确定的，所以使用3维地图
int main() {
    int n, m, p;
    cin >> n >> m >> p;
    vector<vector<int>> a(n,vector<int>(m));
    vector<vector<int>> b(n,vector<int>(m));
    vector<vector<int>> c(n,vector<int>(m));
    vector<vector<vector<int>>> map(n,vector<vector<int>>(m,vector<int>(p-1,-1)));

    for(auto map : {&a,&b}) {
        for(auto& vec : *map) {
            for(auto& v : vec) {
                cin >> v;
            }
        }
    }
    auto px = p-1;
    for(auto i = 0; i < n; i++) {
        for(auto j = 0; j < m; j++) {
            c[i][j] = a[i][j]%px;
        }
    }
    // for(auto& vec : c) {
    //     for(auto v :vec) {
    //         cout << v << " ";
    //     }
    //     cout << endl;
    // }
    vector<pair<int,int>> round = {
        {0,1},{0,-1},{1,0},{-1,0}
    };
    deque<vector<int>> dq;
    dq.push_back({0,0,c[0][0]});
    map[0][0][c[0][0]] = 0;
    while(dq.size()) {
        auto vec = dq.front();
        dq.pop_front();
        auto step = map[vec[0]][vec[1]][vec[2]];        
        for(auto& off : round) {
            int y = vec[0] + off.first;
            int x = vec[1] + off.second;
            if(x < 0 || y < 0 || x >= m || y >= n) {
                continue;
            }
            int q = (vec[2] + c[y][x])%px;
            if(map[y][x][q] != -1) {
                continue;
            }
            map[y][x][q] = step + 1;
            if(y == n-1 && x == m - 1 && q == 0) {
                cout << step + 1 << endl;
                return 0;
            }
            dq.push_back({y,x,q});
        }
    }
    // for(auto k = 0; k < px; k++) {
    //     cout << "{: " << k << endl;
    //     for(auto i = 0; i < n; i++) {
    //         for(auto j = 0; j < m; j++) {
    //             cout << map[i][j][k] << " ";
    //         }
    //         cout << endl;
    //     }
    //     cout << "}" << endl;
    // }
    cout << map[n-1][m-1][0] << endl;
}
// 64 位输出请用 printf("%lld")