[Q] D - Medicines on Grid

普通にBFSを考える

考察
1. DP[i][j] = マス(i, j)に到達したときの最大エネルギーとして管理するとよさそう。
2. 薬を入力するときに、DP[i][j]に薬の値をいれてみる。
3. 最大値の更新があったときに進む、だけだとうまくいかない。
入力で受けた薬マスに入らない判定になってしまうので、到達したかどうかの判定seen[i][j]を用意すればよさそう。
4. マスに進む条件を次の2つにしてAC。
a. 最大エネルギーを更新したか
b. まだ未踏のマスか
最大でO(HWN)見ることになるけど、それでも40000*300で間に合う。

実装

int main()
{
  cincout();

  ll H, W;
  cin >> H >> W;
  vector<string> S(H);
  rep(i, H) cin >> S[i];
  ll sy, sx, ty, tx;
  rep(i, H) rep(j, W)
  {
    if (S[i][j] == 'S')
      sy = i, sx = j;
    if (S[i][j] == 'T')
      ty = i, tx = j;
  }
  ll N;
  cin >> N;

  vector DP(H, vector<ll>(W, -1)); // 到達時の最大エネルギー
  vector seen(H, vector<bool>(W, false)); // いったかどうか
  rep(i, N)
  {
    ll a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    DP[a][b] = max(DP[a][b], c);
  }
  queue<pll> Q;
  Q.push({sy, sx});
  seen[sy][sx] = true;
  while (!Q.empty())
  {
    auto [y, x] = Q.front();
    Q.pop();
    if (DP[y][x] <= 0)
      continue;
    rep(d, 4)
    {
      ll ny = y + dy[d], nx = x + dx[d];
      if (isn_field(ny, nx, H, W))
        continue;
      if (S[ny][nx] == '#')
        continue;
      if (chmax(DP[ny][nx], DP[y][x] - 1)) // 更新があれば、２度目でもいく。
      {
        seen[ny][nx] = true;
        Q.push({ny, nx});
      }
      if (seen[ny][nx])
        continue;
      seen[ny][nx] = true;
      Q.push({ny, nx});
    }
  }
  if (seen[ty][tx] && DP[ty][tx] >= 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

https://atcoder.jp/contests/abc348/submissions/52131170

Dijkstraで考える

本番はこっち。薬をオーバードーズできて無限に探索しちゃうかなって勘違いしてしまった。そんなことなかった。

1. スタート地点から、薬を経由して、ゴールにいけるかどうかを知りたい。Dijkstraが使えそう。
2. 薬とゴールを頂点に見立てて、N+1頂点。
距離は、薬どうし、または薬とゴールまでの、マス上の最短経路とする。
3. グラフを張れば、Sマスの薬IDをstart_idとして、Tマスのgoal_idまでいけるかどうかDijkstraすればいい。

グラフを張るオーダーは、マス目の総和が200 * 200 = 40000
薬の数が300なので、O(HMN) = 40000 * 300で間に合う。

実装

int main()
{
  cincout();

  ll H, W;
  cin >> H >> W;
  vector<string> A(H);
  rep(i, H) cin >> A[i];
  ll N;
  cin >> N;

  ll sy, sx, ty, tx;
  rep(i, H) rep(j, W)
  {
    if (A[i][j] == 'S')
      sy = i, sx = j;
    if (A[i][j] == 'T')
      ty = i, tx = j;
  }

  graph g(N + 1); // Dijkstraのライブラリ
  ll start_id = -1; // 薬が存在するはず。
  ll goal_id = N;
  // 40000 * 300
  vector<tll> medicine(N);
  rep(i, N)
  {
    ll r, c, e;
    cin >> r >> c >> e;
    --r, --c;
    if (r == sy && c == sx)
      start_id = i;
    medicine[i] = {r, c, e};
  }
  // スタートのエネルギーがない
  if (start_id == -1)
  {
    cout << "No" << endl;
    return 0;
  }

  vector<vector<ll>> dist(H, vector<ll>(W, oo)); // dist[0][2] = 薬0から薬2までの最短距離
  rep(i, N)
  {
    auto [r, c, e] = medicine[i];
    dist.assign(H, vector<ll>(W, oo)); // 毎回初期化
    auto init_edges = [&](vector<vector<ll>> &dist)
    {
      // 薬iから薬jと、iからTまでの最短距離をグラフに入れる
      queue<pll> Q;
      Q.push({r, c});
      dist[r][c] = 0;
      while (!Q.empty())
      {
        auto [y, x] = Q.front();
        Q.pop();
        rep(d, 4)
        {
          ll ny = y + dy[d];
          ll nx = x + dx[d];
          if (isn_field(ny, nx, H, W))
            continue;
          if (A[ny][nx] == '#')
            continue;
          if (chmin(dist[ny][nx], dist[y][x] + 1))
            Q.push({ny, nx});
        }
      }
      rep(j, N)
      {
        if (i == j)
          continue;
        auto [r2, c2, e2] = medicine[j];
        // この薬まで到達できるなら、辺を張る
        if (dist[r2][c2] != oo && dist[r2][c2] <= e)
          g.add_edge(i, j, dist[r2][c2]);
      }
      // ゴールに行けるなら、辺を張る
      if (dist[ty][tx] != oo && dist[ty][tx] <= e)
        g.add_edge(i, goal_id, dist[ty][tx]);
    };
    init_edges(dist);
  }
  g.dijkstra(start_id);
  if (g.d[goal_id] == oo)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
}

https://atcoder.jp/contests/abc348/submissions/52114427