コンテンツにスキップ

SamCoding Round 10 (Div. 4) E - Penguins on an Iceberg

サイト
SamCoding
コンテスト
SamCoding Round 10 (Div. 4)
問題
E - Penguins on an Iceberg(常設版)

n×mn \times m のグリッドがあり、各マスは氷(#)、水(.)、ペンギンが乗った氷(P)のどれかです。グリッドの外はすべて水です。毎晩、水と上下左右に隣り合う氷のマスがすべて同時に溶けて水になります。ペンギンが乗ったマスも普通の氷と同じように溶け、その晩にペンギンは水に落ちます。最後のペンギンが何晩目に水に落ちるかを求める問題です(n,m≤1000n, m \le 1000)。

11 晩目に溶けるのは、水またはグリッドの外と隣り合う氷のマスです。22 晩目に溶けるのは、まだ溶けていない氷のうち、11 晩目に溶けたマスと隣り合うマスです。以下同様に、tt 晩目に溶けるマスは t−1t - 1 晩目に溶けたマスから 11 歩で行けるマスになります。

なので、11 晩目に溶けるマスをすべて始点にした多始点 BFS をすれば、各マスが何晩目に溶けるかが求まります。答えは P のマスの値の最大値です。計算量は O(nm)O(nm) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/range.hpp"
void solve() {
LL(N, M);
VS(S, N);
Rect rect(N, M);
vvl dist(N, vl(M, -1));
deque<pl> que;
for (auto [i, j] : rect) {
if (S[i][j] == '.') {
dist[i][j] = 0;
continue;
}
bool f = false;
for (auto [ni, nj] : rect.neighbors4(i, j)) {
if (S[ni][nj] == '.')
f = true;
}
if (len(rect.neighbors4(i, j)) < 4) {
f = true;
}
if (f) {
que.push_back({i, j});
dist[i][j] = 1;
}
}
while (len(que)) {
auto [i, j] = que.front();
que.pop_front();
for (auto [ni, nj] : rect.neighbors4(i, j)) {
if (dist[ni][nj] == -1) {
dist[ni][nj] = dist[i][j] + 1;
que.push_back({ni, nj});
}
}
}
ll ans = 0;
for (auto [i, j] : rect) {
if (S[i][j] == 'P')
chmax(ans, dist[i][j]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

dist[i][j] はマス (i,j)(i, j) が溶ける晩で、水のマスは 00 にしています。Rect は N×MN \times M のマスをまとめて扱う型で、for (auto [i, j] : rect) で全マスを回り、neighbors4(i, j) でグリッド内の上下左右のマスを返します。返ってきたマスが 44 つ未満なら、そのマスはグリッドの端にあり、外の水と隣り合っています。

使用ライブラリ:cpp_include@cb82602