[ABC348] 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