#include<bits/stdc++.h>  // 包含所有常用标准库，竞赛常用
using namespace std;     // 使用std命名空间，避免重复写std::
#define int long long    // 将int类型重定义为long long，防止数值溢出
const int N=12;          // 地图最大尺寸（12x12）
const int MOD=1e4+10;    // 状态中余数的最大模数（适配p-1的范围）

// 全局变量定义
int n,m,p,mod;           // n:地图行数 m:地图列数 p:目标模数 mod:p-1（费马小定理相关）
int a[N][N];             // 存储地图每个位置的数值（路径累加用）
int b[N][N];             // 读取但未使用的第二个矩阵（可能是题目预留参数）
int c[N][N];             // 未使用的临时矩阵
int yu;                  // 未使用的余数临时变量
// dp[x][y][k]: 表示从起点到(x,y)位置，路径数值和模mod等于k时的最小步数
// 初始值-1表示该状态不可达
int dp[N][N][MOD];       
// 方向数组：上下左右四个移动方向（下、右、上、左）
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

// BFS队列中的节点结构体
struct Node{
    int x,y;             // 当前位置的坐标(x,y)
    int counter_part;    // 从起点到当前位置的路径数值和 模mod 的结果
};

// 广度优先搜索(BFS)函数：从起点(sx,sy)到终点(ex,ey)寻找满足条件的最短路径
// 核心逻辑：记录每个位置+余数状态的最短步数
void bfs(int sx,int sy,int ex,int ey){
    // 初始化dp数组为-1，表示所有状态初始不可达
    memset(dp,-1,sizeof(dp));
    queue<Node> q;       // BFS队列，存储待扩展的节点
    
    // 起点初始化：将起点(1,1)入队，初始余数为a[1][1]%mod，步数为0
    q.push({sx,sy,a[sx][sy]%mod});
    dp[sx][sy][a[sx][sy]%mod]=0;
    
    // BFS主循环：队列不为空时持续扩展
    while(!q.empty()){
        Node front=q.front();q.pop();  // 取出队首节点并弹出
        // 当前节点的步数（从起点到该节点的最短步数）
        int dis=dp[front.x][front.y][front.counter_part];
        
        // 遍历四个移动方向
        for(int i=0;i<4;i++){
            // 计算移动后的新坐标
            int tx=front.x+dx[i];
            int ty=front.y+dy[i];
            
            // 边界检查：新坐标在地图范围内（1-based索引）
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
                // 计算新余数：当前余数 + 新位置数值 后模mod
                int counter_part=(front.counter_part+a[tx][ty])%mod;
                // 如果该状态（tx,ty,counter_part）未被访问过
                if(dp[tx][ty][counter_part]==-1){
                    dp[tx][ty][counter_part]=dis+1;  // 步数+1
                    q.push({tx,ty,counter_part});    // 新状态入队
                }
            }
        }
    }
}

// 核心解题函数：处理问题逻辑，调用BFS并输出结果
void solve(){
    mod=p-1;  // 根据数论知识（费马小定理），将模数转为p-1
    // 特判p=1的情况：任何数模1都是0，但题目要求可能无解，直接输出-1
    if(p==1){
        cout<<-1<<endl;
    }else{
        // 调用BFS，从(1,1)到(n,m)搜索最短路径
        bfs(1,1,n,m);
        // 检查终点(n,m)余数为0的状态是否可达
        if(dp[n][m][0]==-1){
            cout<<-1<<endl;  // 不可达输出-1
        }else{
            // 可达则输出最短步数
            cout<<dp[n][m][0]<<endl;
        }
    }
    return;
}

// 主函数：程序入口
signed main(){
    // 加速cin/cout输入输出，避免超时（竞赛常用）
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 输入地图尺寸n,m和目标模数p
    cin>>n>>m>>p;
    // 输入第一个矩阵a[N][N]（路径数值矩阵）
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    // 输入第二个矩阵b[N][N]（代码中未使用，可能是题目备用参数）
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
        }
    }
    
    // 调用解题函数
    solve();
    return 0;
}
总结