TopCoder Desert Wind

/// https://arena.topcoder.com/index.html#/u/practiceCode/1289/1468/1570/1/1289
#include <bits/stdc++.h>

using namespace std;

class DesertWind {
  public:
    int daysNeeded(vector<string> theMap) {
      int N = theMap.size(), M = theMap[0].size();
      const int INF = 0x3f3f3f3f;
      const int di[] = {-1, 0, 1, 0, -1, -1, 1, 1}, dj[] = {0, 1, 0, -1, -1, 1, -1, 1};
      vector<vector<int>> dp(N, vector<int>(M, INF));
      int goal_x = -1, goal_y = -1;
      for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
          if (theMap[i][j] == '@')
            goal_x = i, goal_y = j;
          else
            if (theMap[i][j] == '*')
              dp[i][j] = 0;
      auto inside = [&](int l, int c) -> bool {
        return l >= 0 && c >= 0 && l < N && c < M;
      };
      bool ok = true;
      while (ok) {
        ok = false;
        for (int i = 0; i < N; ++i)
          for (int j = 0; j < M; ++j)
            if (theMap[i][j] != 'X') {
              int best1 = INF, best2 = INF;
              for (int k = 0; k < 8; ++k) {
                int iv = i + di[k], jv = j + dj[k];
                if (!inside(iv, jv))
                  continue;
                int cost = dp[iv][jv] + 1;
                if (cost <= best1) {
                  best2 = best1;
                  best1 = cost;
                } else {
                  if (cost < best2)
                    best2 = cost;
                }
              }
              int best_cost = min(best1 + 2, best2);
              if (best_cost < dp[i][j]) {
                dp[i][j] = best_cost;
                ok = true;
              }
            }
      }
      if (dp[goal_x][goal_y] == INF)
        return -1;
      return dp[goal_x][goal_y];
    }
};