题解 | 走一个大整数迷宫

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int n, m ,p;
int a[11][11];
int dist[11][11][10005];
int direction[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; 

//int vis[11][11][10005];
//struct status {
//	int x;
//	int y;
//	int cost;
//	int modVal;
//};

struct status {
	int x;
	int y;
	int modVal;
};

//看了题解之后照着写了一遍，感觉启发挺大但是还是掌握的有点模模糊糊的
//首先是余数的部分，我原先想的是用费马小定理和快速幂，大概单个数是log(log(b i, j))的时间，但是看了题解直接o(1)就行了，因为这个实际比较特殊，加入一般情况只有条件p, a(底数)互质应该是费马小定理和快速幂
//然后是bfs部分，我原来是怎么也想不通可以往回走不会死循环吗，看了题解之后认为这个搜索就是状态转移，状态一般是不重复(独一无二的)，其不可重复遍历的（为此一般要加上一定的约束，比如最短路径到达该状态...），状态需要时有限的（因此约束了是mod）
int main() {
    cin >> n >> m >> p;
    p--;
	for (int i = 0; i < n; i++)  {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			a[i][j] %= p;
		}
	}
	int tmp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tmp;
		}
	}
	memset(dist, 0xFF, sizeof(dist));
	queue<status> q;
	status st;
	st.x = 0;
	st.y = 0;
	st.modVal = a[st.x][st.y];
	dist[st.x][st.y][st.modVal] = 0;
	q.push(st);
	while (!q.empty()) {
		status s = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x = s.x + direction[i][0];
			int y = s.y + direction[i][1];
			int modVal = (s.modVal + a[x][y]) % p; 
			if (x < n && x > -1 && y < m && y > -1 && dist[x][y][modVal] < 0) {
				status new_s;
				new_s.x = x;
				new_s.y = y;
				new_s.modVal = modVal;
				q.push(new_s);
				dist[x][y][modVal] = dist[s.x][s.y][s.modVal] + 1;
			}
		}
	}
	cout << dist[n - 1][m - 1][0] << endl;
}