ポリゴンがグリッド内に持つ辺の数を調べるC++プログラム

次元hxwのグリッドが与えられていると仮定します。グリッドには、白と黒の2種類のセルがあります。白いセルは「。」で表され、黒いセルは「＃」で表されます。これで、グリッドにはポリゴンを形成する複数の黒いセルが含まれます。ポリゴンの辺の数を調べる必要があります。グリッドの最も外側のセルは常に白であることに注意してください。

したがって、入力がh =4、w =4、grid ={"...."、 "。##。"、 "。##。"、 "...."}の場合、出力は4になります。

黒いセルは正方形を形成し、正方形には4つの辺があります。

ステップ

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

sides := 0
for initialize i := 1, when i < h, update (increase i by 1), do:
   for initialize j := 1, when j < w, update (increase j by 1), do:
      bl := 0
      if grid[i - 1, j - 1] is same as '#', then:
         (increase bl by 1)
      if grid[i - 1, j] is same as '#', then:
         (increase bl by 1)
      if grid[i, j - 1] is same as '#', then:
         (increase bl by 1)
      if grid[i, j] is same as '#', then:
         (increase bl by 1)
      if bl is same as 1 or 3, then:
         (increase sides by 1)
return sides

例

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

#include <bits/stdc++.h>
using namespace std;
void solve(int h, int w, vector<string> grid){
   int sides = 0;
   for(int i = 1; i < h; i++) {
      for(int j = 1; j < w; j++) {
         int bl = 0;
         if(grid.at(i - 1).at(j - 1) == '#') {
            bl++;
         }
         if(grid.at(i - 1).at(j) == '#') {
            bl++;
         }
         if(grid.at(i).at(j - 1) == '#') {
            bl++;
         }
         if(grid.at(i).at(j) == '#') {
            bl++;
         }
         if(bl == 1 or bl == 3) {
            sides++;
         }
      }
   }
   cout << sides;
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"....", ".##.", ".##.", "...."};
   solve(h, w, grid);
   return 0;
}

入力

4, 4, {"....", ".##.", ".##.", "...."}

出力

4