グリッド内で照らされているセルの数を求めるC++プログラム

問題の概要

ここでは、縦 h × 横 w のサイズを持つグリッドが与えられたとき、光で照らされているセルの数を求めるC++プログラムを紹介します。グリッドのセルには「電球」または「障害物」が置かれています。電球のあるセルは、そのセル自身と上下左右のセルを照らし、光は障害物に遮られない限りまっすぐ伝わっていきます。一方、障害物のあるセルは照らされることがなく、電球の光を遮って他のセルへ光が届かないようにします。電球の位置を配列 bulb、障害物の位置を配列 obstacles として受け取り、グリッド全体で照らされているセルの合計数を求めます。

たとえば、入力が h = 4、w = 4、bulb = {{1, 1}, {2, 2}, {3, 3}}、obstacle = {{0, 0}, {2, 3}} の場合、出力は 13 になります。

上の図を見ると、グリッド内でどのセルが照らされているのかがひと目で分かります。

解法のアプローチ

この問題は、各行・各列を両方向から走査することで効率的に解くことができます。手順は以下の通りです。

1. 電球のセルには 1、障害物のセルには 2 を格納した 2 次元配列 grid を作成します。
2. 結果を表す変数 result を全セル数 h × w で初期化します。これは「すべてのセルが照らされている」と仮定し、後から照らされていないセルの数を差し引いていく方針です。
3. 各行について、左から右、および右から左の 2 回の走査を行います。走査中はフラグ gd を管理し、障害物（値が 2）に遭遇すると gd を 0 にリセット、電球（値が 1）に遭遇すると gd を 1 にセットします。この値を check 配列に OR 演算で記録していきます。
4. 同様に、各列についても上から下、下から上の 2 回の走査を行い、同じ要領で check 配列を更新します。
5. 最後に、check[i][j] が false になっているセル（どの方向からも光が届いていないセル）の数を result から引いたものが答えとなります。

C++での実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int h, int w, vector<pair<int, int>> bulb, vector<pair<int, int>> obstacle){
   int bulbSize = bulb.size();
   int blockSize = obstacle.size();
   vector<vector<int>> grid(h, vector<int>(w, 0));
   for (int i = 0; i < bulbSize; i++) {
      int x = bulb[i].first;
      int y = bulb[i].second;
      grid[x][y] = 1;
   }
   for (int i = 0; i < blockSize; i++) {
      int x = obstacle[i].first;
      int y = obstacle[i].second;
      grid[x][y] = 2;
   }
   int result = h * w;
   vector<vector<bool>> check(h, vector<bool>(w, 0));
   for (int i = 0; i < h; i++) {
      bool gd = 0;
      for (int j = 0; j < w; j++) {
         if (grid[i][j] == 2)
            gd = 0;
         if (grid[i][j] == 1)
            gd = 1;
         check[i][j] = check[i][j] | gd;
      }
      gd = 0;
      for (int j = w - 1; j >= 0; j--) {
         if (grid[i][j] == 2)
            gd = 0;
         if (grid[i][j] == 1)
            gd = 1;
         check[i][j] = check[i][j] | gd;
      }
   }
   for (int j = 0; j < w; j++) {
      bool k = 0;
      for (int i = 0; i < h; i++) {
         if (grid[i][j] == 2)
            k = 0;
         if (grid[i][j] == 1)
            k = 1;
         check[i][j] = check[i][j] | k;
      }
      k = 0;
      for (int i = h - 1; i >= 0; i--) {
         if (grid[i][j] == 2)
            k = 0;
         if (grid[i][j] == 1)
            k = 1;
         check[i][j] = check[i][j] | k;
      }
   }
   for (int i = 0; i < h; i++)
      for (int j = 0; j < w; j++)
         result -= !check[i][j];
   return result;
}
int main() {
   int h = 4, w = 4;
   vector<pair<int, int>> bulb = {{1, 1}, {2, 2}, {3, 3}}, obstacle = {{0, 0}, {2, 3}};
   cout<< solve(h, w, bulb, obstacle);
   return 0;
}

計算量

各行と各列をそれぞれ 2 方向から走査しているため、時間計算量は O(h × w) です。また、grid と check の 2 つの 2 次元配列が必要となるため、空間計算量も O(h × w) となります。

実行結果

入力：

4, 4, {{1, 1}, {2, 2}, {3, 3}}, {{0, 0}, {2, 3}}

出力：

13