โปรแกรม C++ หาจำนวนด้านของรูปหลายเหลี่ยมในกริด

กำหนดกริด h × w มีเซลล์สีขาว (.) และสีดำ (#) เซลล์สีดำรวมกันเป็นรูปหลายเหลี่ยม (ขอบนอกสุดของกริดเป็นสีขาวเสมอ) ต้องการหาจำนวนด้านของรูปหลายเหลี่ยมนั้น

ตัวอย่าง: h=4, w=4, grid={"....", ".##.", ".##.", "...."} ผลลัพธ์: 4 (เป็นสี่เหลี่ยมจัตุรัส มี 4 ด้าน)

ขั้นตอนการแก้ปัญหา

1. วนลูป i = 1 ถึง h-1, j = 1 ถึง w-1 (ดูบล็อก 2×2)
2. นับ bl = จำนวนเซลล์สีดำในบล็อก 2×2 ที่มุม (i-1,j-1), (i-1,j), (i,j-1), (i,j)
3. ถ้า bl == 1 หรือ bl == 3 เพิ่ม sides++ (เพราะมุมของรูปหลายเหลี่ยมเกิดขึ้นที่จุดนี้)
4. คืนค่า sides

ตัวอย่างโค้ด C++

#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[i-1][j-1] == '#') bl++;
            if (grid[i-1][j] == '#') bl++;
            if (grid[i][j-1] == '#') bl++;
            if (grid[i][j] == '#') bl++;
            if (bl == 1 || bl == 3) sides++;
        }
    }
    cout << sides;
}

int main() {
    int h = 4, w = 4;
    vector<string> grid = {"....", ".##.", ".##.", "...."};
    solve(h, w, grid);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, 4, {"....", ".##.", ".##.", "...."}

Output: 4