P9904 [COCI 2023/2024 #1] Labirint 题解

题目传送门

解题思路

看到这种题目，感觉只能暴力或者暴力优化通过。

考虑记忆化搜索，首先设 $d{p}_{i,j,s}$ 表示走到第 $i$ 行，第 $j$ 列时，遇到的所有颜色 $s$。这里我们使用了二进制数表示遇到的所有颜色，比如串 $0110$ 表示遇到了第 $2,3$ 种颜色。

我们设 $(x,y)$ 表示可以通过 $(i,j)$ 得到的单元格。那么 $d{p}_{i,j,s}=\underset{|x-i|+|y-j|\le 1}{\min }d{p}_{x,y,s\text{or}{2}^{to(a_{x,y})}}$，其中 $\text{or}$ 表示或运算，$to(x)$ 表示字符 $x$ 所对应的颜色编号（可以自己定义）。关于 $s$ 的操作：如果 $s$ 为 $1010$，$to(x)=2$，那么 $s\text{or}{2}^2$，那么 $s$ 就变成了 $1110$。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
char a[110][110], b[110][110];
int n, m, sx, sy, ex, ey, cnt;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int k[10];
inline int geto(char a) {if (a == 'P') {return 0;} else if (a == 'C') {return 1;} else if (a == 'Z') {return 2;}return 3;
}
int ans;
int dp[110][110][(1 << 4) + 10];
inline int dfs(int x, int y, int res) {if (x == ex && y == ey) {return dp[x][y][res] = ((res & 1) != 0) + ((res & 2) != 0) + ((res & 4) != 0) + ((res & 8) != 0);}if (dp[x][y][res] != 5) {return dp[x][y][res];}dp[x][y][res] = 6;
//	cout << x << ' ' << y << endl;for (int i = 0; i < 4; i++) {int xx = x + dx[i];int yy = y + dy[i];if (xx > 0 && yy > 0 && xx <= n && yy <= m) {int p;if (abs(xx - x) == 1) {p = geto(b[min(x, xx)][y]);} else {p = geto(a[x][min(y, yy)]);}int now = res | (1 << p);dp[x][y][res] = min(dp[x][y][res], dfs(xx, yy, now));}}return dp[x][y][res];
}
signed main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j < m; j++) {cin >> a[i][j];}}for (int i = 1; i < n; i++) {for (int j = 1; j <= m; j++) {cin >> b[i][j];}}int q;cin >> q;while (q--) {cin >> sx >> sy >> ex >> ey;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {for (int k = 0; k <= 16; k++) {dp[i][j][k] = 5;}}}cout << dfs(sx, sy, 0) << "\n";}return 0;
}