โปรแกรม C++ นับจำนวนเซลล์ที่ถูกส่องสว่างโดยหลอดไฟหลายดวง

กำหนดกริด h × w มีหลอดไฟหลายดวง (ในอาร์เรย์ bulb) และอุปสรรค (ในอาร์เรย์ obstacle) หลอดส่องสว่างตัวเองและ 4 ทิศทาง จนกว่าจะเจออุปสรรค อุปสรรคบังแสงและไม่ถูกส่อง ต้องการหาจำนวนเซลล์ทั้งหมดที่ถูกส่องสว่าง

ตัวอย่าง: h=4, w=4, bulb={{1,1},{2,2},{3,3}}, obstacle={{0,0},{2,3}} ผลลัพธ์: 13

ขั้นตอนการแก้ปัญหา (Sweep 4 ทิศทาง)

1. สร้างกริด grid ค่า 0=ว่าง, 1=หลอด, 2=อุปสรรค
2. อาร์เรย์ check บูลีน เก็บว่าเซลล์ถูกส่องหรือไม่
3. สแกนแถวซ้าย→ขวา: ตัวแปร gd บอกว่ากำลังถูกส่องจากซ้ายหรือไม่ (เจอหลอด=1, เจออุปสรรค=0) OR เข้า check
4. สแกนแถวขวา→ซ้าย: เหมือนกัน
5. สแกนคอลัมน์บน→ล่าง: ตัวแปร k OR เข้า check
6. สแกนคอลัมน์ล่าง→บน: เหมือนกัน
7. นับเซลล์ที่ check == false ลบออกจาก h*w ได้คำตอบ

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

#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++)
        grid[bulb[i].first][bulb[i].second] = 1;
    for (int i = 0; i < blockSize; i++)
        grid[obstacle[i].first][obstacle[i].second] = 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}};
    vector<pair<int, int>> obstacle = {{0, 0}, {2, 3}};
    cout << solve(h, w, bulb, obstacle);
    return 0;
}

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

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

Output: 13