Chương trình C ++ để tìm ra số cạnh của một đa giác bên trong một lưới

Giả sử, chúng ta được cung cấp một lưới có kích thước h x w. Có hai loại ô trong lưới, ô trắng và ô đen. Các ô màu trắng được biểu thị bằng ".", Trong khi các ô màu đen được biểu thị bằng "#". Bây giờ lưới có nhiều ô màu đen trong đó tạo thành một đa giác. Chúng ta phải tìm ra số cạnh của đa giác. Cần lưu ý rằng các ô ngoài cùng của lưới luôn có màu trắng.

Vì vậy, nếu đầu vào giống như h =4, w =4, grid ={"....", ". ##.", ". ##.", "...."}, thì đầu ra sẽ là 4.

Các ô màu đen tạo thành một hình vuông và một hình vuông có 4 cạnh.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

4