题意
给定一个 n\times m 的四联通网格，通过每一对相邻的单元格之间的门移动到其它单元格，门有四种颜色：蓝、红、绿、橙，分别用字符 P、C、Z、N 表示。
# 思路
- Subtask1：在 $n = 1$ 时，$2$ 个单元格之间的路径是唯一的，直接跑 $2$ 点之间的路径，用 `bool color[]` 来记录路径是否存在某个颜色的门（存在为 $1$，否则为 $0$），用 `num` 统计门的颜色数，时间复杂度 $O(qm)$。
- Subtask2+Subtask3：都是只包含 `P` 和 `C`，可以认为 Subtask2 是 Subtask3 的一种特殊情况，对于 Subtask2 其实只用判断 $2$ 个单元格是否在同行或同列就行了（是则答案为 $1$,否则答案为 $2$）；我们直接解决 Subtask3，用 dfs 实现洪水填充，用 `bool vis[][]` 记录状态，先跑 $1$ 遍只通过 `P`，可以到达则答案为 $1$，反之再跑 $1$ 遍只通过 `C`，可以到达则答案为 $1$，否则为 $0$，时间复杂度 $O(qnm)$（不含常数）。
- AC：由于本题数据范围很小，考虑枚举经过哪些颜色的门的情况，加上不经过门和经过所有颜色的门共 $16$ 种，同 Subtask2+Subtask3 用 dfs 实现洪水填充，跑 $16$ 遍 dfs 取经过门的颜色数的最小值，在不经过门时特判跳过，经过所有颜色的门时也可以特判跳过但是由于特判编写更为费事且该做法时间复杂度同 Subtask2+Subtask3（不含常数），不写特判可以 AC，`bool door[]` 记录情况，`bool vis[][]` 记录状态。
# Code:
### 11pts(Subtask1) 主要代码
```cpp
cin >> n >> m;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m - 1; ++j) cin >> color_n[i][j];
for (int i = 1; i <= n - 1; ++i) for (int j = 1; j <= m; ++j) cin >> color_m[i][j];
cin >> q;
for (int i = 1; i <= q; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (n == 1) {
int num = 0;
memset(color, 0, sizeof(color));
for (int j = min(b, d); j < max(b, d); ++j) {
if(color_n[1][j] == 'P' && ! color[1]) {
color[1] = 1;
num++;
} else if(color_n[1][j] == 'C' && ! color[2]) {
color[2] = 1;
num++;
} else if(color_n[1][j] == 'Z' && ! color[3]) {
color[3] = 1;
num++;
} else if (! color[4]) {
color[4] = 1;
num++;
}
}
cout << num << '\n';
}
}
```
### 37pts(Subtask2+Subtask3) 主要代码
```cpp
void dfs1(int x, int y) {
vis[x][y] = 1;
if(x < n) if (! vis[x + 1][y]) if(color_m[x][y] == 'P') dfs1(x + 1, y);
if(y < m) if (! vis[x][y + 1]) if(color_n[x][y] == 'P') dfs1(x, y + 1);
if(x > 1) if (! vis[x - 1][y]) if(color_m[x - 1][y] == 'P') dfs1(x - 1, y);
if(y > 1) if (! vis[x][y - 1]) if(color_n[x][y - 1] == 'P') dfs1(x, y - 1);
return;
}
void dfs2(int x, int y) {
vis[x][y] = 1;
if(x < n) if (! vis[x + 1][y]) if(color_m[x][y] == 'C') dfs2(x + 1, y);
if(y < m) if (! vis[x][y + 1]) if(color_n[x][y] == 'C') dfs2(x, y + 1);
if(x > 1) if (! vis[x - 1][y]) if(color_m[x - 1][y] == 'C') dfs2(x - 1, y);
if(y > 1) if (! vis[x][y - 1]) if(color_n[x][y - 1] == 'C') dfs2(x, y - 1);
return;
}
memset(vis, 0, sizeof(vis));
dfs1(a, b);
if (vis[c][d] == 1) cout << 1 << '\n';
else {
memset(vis, 0, sizeof(vis));
dfs2(a, b);
if (vis[c][d] == 1) cout << 1 << '\n';
else cout << 2 << '\n';
}
```
### 70ptsAC 完整代码
``` cpp
#include<bits/stdc++.h>
using namespace std;
int n, m, q;
char color_n[110][110], color_m[110][110];
bool door[100], vis[110][110];
void dfs(int x, int y) {
vis[x][y] = 1;
if(x < n) if (! vis[x + 1][y]) if(door[color_m[x][y]] == 1) dfs(x + 1, y);
if(y < m) if (! vis[x][y + 1]) if(door[color_n[x][y]] == 1) dfs(x, y + 1);
if(x > 1) if (! vis[x - 1][y]) if(door[color_m[x - 1][y]] == 1) dfs(x - 1, y);
if(y > 1) if (! vis[x][y - 1]) if(door[color_n[x][y - 1]] == 1) dfs(x, y - 1);
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m - 1; ++j) cin >> color_n[i][j];
for (int i = 1; i <= n - 1; ++i) for (int j = 1; j <= m; ++j) cin >> color_m[i][j];
cin >> q;
for (int i = 1; i <= q; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int ans = 4;
for (int P = 0; P <= 1; ++P) {
for (int C = 0; C <= 1; ++C) {
for (int Z = 0; Z <= 1; ++Z) {
for (int N = 0; N <= 1; ++N) {
int one = 0;
if (P == 1) one++;
if (C == 1) one++;
if (Z == 1) one++;
if (N == 1) one++;
if (one == 0) continue;
memset(vis, 0, sizeof(vis));
door['P'] = P;
door['C'] = C;
door['Z'] = Z;
door['N'] = N;
dfs(a, b);
if (vis[c][d] == 1) ans = min(ans, one);
}
}
}
}
cout << ans << '\n';
}
}
```