C++ 그리드 내부에 폴리곤의 변의 수를 찾는 프로그램

<시간/>

h x w 차원의 그리드가 주어졌다고 가정합니다. 그리드에는 흰색 셀과 검은색 셀의 두 가지 유형의 셀이 있습니다. 흰색 셀은 '.'로 표시되고 검은색 셀은 '#'으로 표시됩니다. 이제 그리드에는 다각형을 형성하는 여러 개의 검은색 셀이 있습니다. 다각형의 변의 수를 알아야 합니다. 그리드의 가장 바깥쪽 셀은 항상 흰색입니다.

따라서 입력이 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, {"....", ".##.", ".##.", "...."}