題目描述

給一個 $n\times m$ 矩陣迷宮， 第 $i$ 行第 $j$ 列的值為 $c_{i,j}$ ，$LH$ 在迷宮中迷路了，他需要你的幫助。

$LH$ 當前在 $(1,1)$ 的位置，出口在 $(n,m)$，這個迷宮有一個計數器，只有當計數器的值模 $(p?1)$ 的余數為 $0$ 時迷宮出口才會開門（出口沒有開門意味著即使在 $(n,m)$ 的位置也不能逃出去）。

$LH$ 每一秒會向迷宮的上下左右四個方向走一步（不可以不走），并且不能走出迷宮的邊界，假設 $LH$ 從 $(i,j)$ 走到了 $(i^{\prime },j^{\prime })$，然后計數器將會加上 $c_{i^{\prime },j^{\prime }}$。

特別的，計數器初始是 $c_{1,1}$。

$c_{i,j}=a_{i,j}\times p^{2^{b_{i,j}}}$。

現在 $LH$ 問你，他最快需要多久才可以走出迷宮。

輸入描述

第一行輸出三個整數 $n,m,p(1\le n,m\le 10,2\le p\le 10^4)$。
接下來輸入一個 $n$ 行 $m$ 列的矩陣 $a_{i,j}$。
接下來輸入一個 $n$ 行 $m$ 列的矩陣 $b_{i,j}$。
$0\le a_i,b_i\le 10^6$。

做法

• 注意到要在模 p-1 意義下，因為 $a^b\%p=(a\%p{)}^b\%p$ ，所以 $c_{i,j}=a_{i,j}\%(p?1)$

• 如此走一遍 bfs 即可

Trick

• 這題如此簡單，那么為什么要放到 trick 專欄呢

• 注意下面代碼 :

  void Show(){while(q.size()){// auto &[x, y, v] = q.front(); q.pop();auto [x, y, v] = q.front(); q.pop();// cout << x << ' ' << y << ' ' << v << ' ' << d[x][y][v] << '\n';for(int i = 0; i < 4; i ++){int a = x + dx[i];int b = y + dy[i];if(a >= 1 && a <= n && b >= 1 && b <= m){int tmpV = (v + A[a][b]) % (p - 1);if(d[a][b][tmpV] == -1){d[a][b][tmpV] = d[x][y][v] + 1;q.push({a, b, tmpV});}}}}
  }
  

• 可以看到，這是一個帶 pop 的數據結構，這種數據結構進行結構化綁定的時候一定不要加 & ，雖然現在看很 NT，但是寫的時候就是容易注意不到，所以放到 trick 專欄里面