给定一个 \(n\times m\) 的地图, '@' 表示你所在的位置, '-' 表示这是沙地, '*' 表示绿洲, 'X' 表示不可到达。你每天可以向周围八格移动,同时每天风也有八个方向,若你恰好逆风行走,则一段路程需要走三天,否则只用走一天。你可以预知今后每天的风向,求所有今后风向情况中,你至多会走多少天才能到达任何一个绿洲,无解返回 \(-1\) 。
\(n,\ m\leq50\)
dp,最短路
令 \(f_{i,\ j}\) 表示从 \((i,\ j)\) 走到任意一个绿洲所需的最小天数。该状态可以从八个方向转移而来,最坏情况下风向可能恰好使得当前转移的最优解逆风行走,此时可以记录当前转移的次优解,所以 \(f_{i,\ j}=\min(s0+3,\ s1+1)\) ,其中 \(s0\) 为最优解, \(s1\) 为次优解。
可以发现这样转移的 dp 有环,可以考虑用最短路求答案。此题可以像 dijkstra 一样松弛 \(n\times m\) 次,每次松弛更新所有 \(f_{i,\ j}\) 的答案。
时间复杂度 \(O(n^2m^2)\)
代码
#includeusing namespace std;const int maxn = 55;const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1}, dy[] = {0, 1, 0, -1, 1, 1, -1, -1};char a[maxn][maxn];int n, m, f[maxn][maxn];struct DesertWind { int daysNeeded(vector field) { int Sx, Sy; n = field.size(); m = field[0].size(); memset(f, 0x3f, sizeof f); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] = field[i][j]; if (a[i][j] == '*') f[i][j] = 0; if (a[i][j] == '@') Sx = i, Sy = j; } } for (int T = 0; T < n * m; T++) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 'X') continue; int v1 = 2e9, v2 = 2e9; for (int k = 0; k < 8; k++) { int x = i + dx[k], y = j + dy[k]; if (x < 0 || y < 0 || x >= n || y >= m) continue; if (v1 > f[x][y]) { v2 = v1, v1 = f[x][y]; } else if (v2 > f[x][y]) { v2 = f[x][y]; } } f[i][j] = min(f[i][j], min(v1 + 3, v2 + 1)); } } } return f[Sx][Sy] > 1e9 ? -1 : f[Sx][Sy]; }} Winnie_the_Pooh;int main() { printf("%d\n", Winnie_the_Pooh.daysNeeded({"*--X-----", "--XX--@--", "*-X------"})); return 0;}