给定一个 \(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)\)

代码

#include 
    
     using 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;}