D-走一个大整数迷宫（牛客月赛97）

题意：给两个n行m列的矩阵a和b，计数器，只有当计数器的值模（p-1）时出口才打开，要从左上走到右下，求最快多久走出迷宫。

分析：无论2的bij次方有多大p的2的bij次方的次方取模（p-1）都为1，所以cij=aij。用bfs搜索最短路径

代码：

#include<bits/stdc++.h>
using namespace std;
struct A{
    int x,y,pp;
};
int dx[4]{-1,1,0,0},dy[4]={0,0,-1,1};
int main(){
    int n,m,p;cin>>n>>m>>p;p--;
    int a[n+10][m+10],b[n+10][m+10];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
        }
    }
    int dp[15][15][10100],vis[15][15][10100];
    vis[1][1][a[1][1]%p]=1;
    dp[1][1][a[1][1]%p]=0;
    queue<A>pru;
    pru.push({1,1,a[1][1]%p});
    while(!pru.empty()){
        auto u=pru.front();
        pru.pop();
        for(int i=0;i<=3;i++){
            int tx=u.x+dx[i],ty=u.y+dy[i],tp=(u.pp+a[tx][ty])%p;
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!vis[tx][ty][tp]){
                vis[tx][ty][tp]=1;
                dp[tx][ty][tp]=dp[u.x][u.y][u.pp]+1;
                pru.push({tx,ty,tp});
            }
        }
    }
    if(!vis[n][m][0])cout<<"-1"<<endl;
    else cout<<dp[n][m][0]<<endl;
    
    return 0;
}