これも実はよくある典型問題だったりはする。
問題概要
下のような の二次元グリッドが与えられる。
#..#.. .....# ....#. #.#...
このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす範囲は
- 光源から上方向に行って最初に壁に遮られるまでの範囲
- 光源から下方向に行って最初に壁に遮られるまでの範囲
- 光源から左方向に行って最初に壁に遮られるまでの範囲
- 光源から右方向に行って最初に壁に遮られるまでの範囲
である。どのマスに光源を置けば照らすマス数を最大化できるか、その最大値を求めよ。
制約
方針
各マスに対して
- 左にどこまで行ったら壁にぶつかるか
- 右にどこまで行ったら壁にぶつかるか
- 上にどこまで行ったら壁にぶつかるか
- 下にどこまで行ったら壁にぶつかるか
を求めることができれば、それを利用して問題を解くことができそうである。ここではまず「左にどこまで行ったら壁にぶつかるか」を効率よく求める方法を考える。
どこまで行ったら壁にぶつかるか
下図は、「各マスについて、そこから左にどこまで行ったら壁にぶつかるか」を表している。実はこれを求めるのはとても典型的な処理だったりする。
これを愚直に求めたいと思ったら
- 各マスに対して ( 通り)
- 左側に目一杯進む (最悪 )
ということで の計算時間がかかってしまう。しかしこれは上手くやることで の計算時間で処理することができる。
まず、各行について独立にやっていいことに注意する。よって、下図のような一次元配列の場合ができれば OK。
これは実は簡単で、以下のようにするだけで実装できる。すなわち cur という変数に、「最後の壁から何マス来たのか」という情報を格納しておいて、各 i に対して
- i マス目が壁だったら、cur = 0 に戻る
- i マス目が通路だったら、cur をインクリメントする
とするだけで実装できる。
int num[]; int cur = 0; for (int i = 0; i < W; ++i) { if ( i が壁 ) cur = 0; else ++cur; num[i] = cur; }
今回の問題
さて、今回の問題では、これをほんの少し応用するだけでできる。今我々は
- 各マスから左側に何マス行ったら壁にぶつかるか (left[i][j] とする)
を求めたが、同様に頑張れば
- 各マスから右側に何マス行ったら壁にぶつかるか (right[i][j] とする)
- 各マスから上側に何マス行ったら壁にぶつかるか (up[i][j] とする)
- 各マスから下側に何マス行ったら壁にぶつかるか (down[i][j] とする)
を求めることもできる。そうすれば、各マスに光源を置いたときに照らす範囲は
- left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
と求めることができる。「-3」をしているのは、left, right, up, down でそれぞれ「光源が置いてあるマスそれ自体」を 4 回足しているから。
#include <iostream> #include <vector> #include <string> using namespace std; int H, W; vector<string> fi; int Left[2100][2100], Right[2100][2100], Up[2100][2100], Down[2100][2100]; int main() { // 入力 cin >> H >> W; fi.resize(H); for (int i = 0; i < H; ++i) cin >> fi[i]; // 前処理 for (int i = 0; i < H; ++i) { int cur = 0; for (int j = 0; j < W; ++j) { if (fi[i][j] == '#') cur = 0; else ++cur; Left[i][j] = cur; } } for (int i = 0; i < H; ++i) { int cur = 0; for (int j = W-1; j >= 0; --j) { if (fi[i][j] == '#') cur = 0; else ++cur; Right[i][j] = cur; } } for (int j = 0; j < W; ++j) { int cur = 0; for (int i = 0; i < H; ++i) { if (fi[i][j] == '#') cur = 0; else ++cur; Up[i][j] = cur; } } for (int j = 0; j < W; ++j) { int cur = 0; for (int i = H-1; i >= 0; --i) { if (fi[i][j] == '#') cur = 0; else ++cur; Down[i][j] = cur; } } // 集計 int res = 0; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (fi[i][j] == '#') continue; res = max(res, Left[i][j] + Right[i][j] + Up[i][j] + Down[i][j] - 3); } } cout << res << endl; }