https://atcoder.jp/contests/abc151/tasks/abc151_d
前提知識
解説
https://atcoder.jp/contests/abc151/submissions/9458353
制約を見るとかなり小さい。
なので、なるべく全探索できるものは、全探索していこう。
任意の二点間の最短距離の最大値を求めるが、任意の二点間の全探索を考えよう。
この段階で、204くらいの組み合わせがある。
二点間の最短距離を求めるには、BFSでO(WH)で行うことができるので、これを毎回やると、
206くらいが計算量となる。
これは、間に合うだろうか。
16*106なので、正直間に合う気もする。
が、ちょっと心配なので、もう少し工夫することを考える。
BFSによる最短距離で求めることができるのは、ある点を始点としたときの他のすべての点の最短距離である。
よって、任意の二点間を全探索するのではなく、始点のみ全探索すれば、BFSすることで全ての終点が見られる。
なので、始点だけ全探索すればいい。
これで204くらいに計算量が落ちるので、十分間に合う。
int H, W; string S[20]; //--------------------------------------------------------------------------------------------------- int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 }; vector<vector<int>> bfs(int sx, int sy) { queue<pair<int, int>> que; vector<vector<int>> res(H, vector<int>(W, inf)); vector<vector<bool>> vis(H, vector<bool>(W, false)); res[sy][sx] = 0; vis[sy][sx] = true; que.push({ sx, sy }); while (!que.empty()) { int x, y; tie(x, y) = que.front(); que.pop(); rep(d, 0, 4) { int xx = x + dx[d]; int yy = y + dy[d]; if (0 <= xx and xx < W and 0 <= yy and yy < H) { if (S[yy][xx] != '#' and !vis[yy][xx]) { res[yy][xx] = res[y][x] + 1; vis[yy][xx] = true; que.push({xx, yy}); } } } } return res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W; rep(y, 0, H) cin >> S[y]; int ans = 0; rep(sx, 0, W) rep(sy, 0, H) if(S[sy][sx] != '#') { auto res = bfs(sx, sy); rep(x, 0, W) rep(y, 0, H) if (S[y][x] != '#') chmax(ans, res[y][x]); } cout << ans << endl; }