グリッド内の照らされたセルの数を見つけるためのC++プログラム

次元h*wのグリッドが与えられていると仮定します。グリッド内のセルには、球根または障害物のいずれかを含めることができます。電球のセルはそれ自体とその右、左、上、下のセルを照らし、障害物のセルが光を遮らない限り、光はセルを通して輝くことができます。障害物セルは照明できず、電球セルからの光が他のセルに到達するのを防ぎます。したがって、配列「bulb」内のグリッド内の電球セルの位置と配列「obstacles」内の障害物セルの位置を考えると、照らされているグリッド内のセルの総数を見つける必要があります。

したがって、入力がh =4、w =4、bulb ={{1、1}、{2、2}、{3、3}}、障害物={{0、0}、{2、3 }}の場合、出力は13になります。

画像から、グリッド内の照らされた細胞を見ることができます。

これを解決するには、次の手順に従います-

bulbSize := size of bulb
blockSize := size of obstacle
Define one 2D array grid
for initialize i := 0, when i < bulbSize, update (increase i by 1), do:
   x := first value of bulb[i]
   y := second value of bulb[i]
   grid[x, y] := 1
for initialize i := 0, when i < blockSize, update (increase i by 1), do:
   x := first value of obstacle[i]
   y := first value of obstacle[i]
   grid[x, y] := 2
result := h * w
Define one 2D array check
for initialize i := 0, when i < h, update (increase i by 1), do:
   gd := 0
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if grid[i, j] is same as 2, then:
         gd := 0
      if grid[i, j] is same as 1, then:
         gd := 1
      check[i, j] := check[i, j] OR gd
   gd := 0
   for initialize j := w - 1, when j >= 0, update (decrease j by 1), do:
      if grid[i, j] is same as 2, then:
         gd := 0
      if grid[i, j] is same as 1, then:
         gd := 1
      check[i, j] := check[i, j] OR gd
for initialize j := 0, when j < w, update (increase j by 1), do:
   k := 0
   for initialize i := 0, when i < h, update (increase i by 1), do:
      if grid[i, j] is same as 2, then:
         k := 0
      if grid[i, j] is same as 1, then:
         k := 1
      check[i, j] := check[i, j] OR k
   k := 0
   for initialize i := h - 1, when i >= 0, update (decrease i by 1), do:
      if grid[i, j] is same as 2, then:
         k := 0
      if grid[i, j] is same as 1, then:
         k := 1
     check[i, j] := check[i, j] OR k
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      result := result - NOT(check[i, j])
return result

例

理解を深めるために、次の実装を見てみましょう-

#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;
}

入力

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

出力

13