题解 | 走一个大整数迷宫

package main

import (
	"fmt"
)

type State struct {
	i, j int
	r    int // 当前计数器 mod (p-1)
	steps int
}

func main() {
	var n, m, p int
	fmt.Scanf("%d %d %d", &n, &m, &p)

	// 读取 a[i][j]
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, m)
		for j := 0; j < m; j++ {
			fmt.Scanf("%d", &a[i][j])
		}
	}

	// 读取 b[i][j]，但不需要使用
	var tmp int
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Scanf("%d", &tmp)
		}
	}

	mod := p - 1
    if mod == 0{
        fmt.Println(-1)
        return
    }

	// dist[i][j][r] 表示到达 (i,j) 且余数为 r 的最小步数
	dist := make([][][]int, n)
	for i:=0;i<n;i++{
        dist[i]= make([][]int, m)
        for j:=0;j<m;j++{
            dist[i][j] = make([]int, mod)
            for k:=0;k<mod;k++{
                dist[i][j][k] = -1
            }
        }
    }

    direction := [][]int{{1,0},{0,-1},{-1,0},{0,1}}

    queue := []State{}
    startR := a[0][0] % mod
    dist[0][0][startR] = 0
    queue = append(queue, State{0,0,startR,0})

    for len(queue) > 0{
        cur := queue[0]
        queue = queue[1:]

        if cur.i == n-1 && cur.j == m-1 && cur.r == 0{
            fmt.Println(cur.steps)
            return
        }

        // 四个方向
        for _, v := range direction {
            ni, nj := cur.i + v[0], cur.j+v[1]
            if ni < 0 || ni >=n || nj<0 || nj>=m {
                continue
            }
            newR := (cur.r + a[ni][nj])%mod
            if dist[ni][nj][newR] == -1{
                dist[ni][nj][newR] = cur.steps +1
                queue = append(queue, State{ni,nj,newR,cur.steps + 1})
            }
        }
    }
    fmt.Println(-1)
}