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

กำหนดกริด h × w ที่มีอุปสรรค (#) และช่องว่าง (.) มีหลอดไฟเพียง 1 ดวง วางได้ที่ช่องว่างเท่านั้น หลอดส่องสว่าง 4 ทิศทาง (ซ้าย ขวา บน ล่าง) จนกว่าจะเจออุปสรรคหรือขอบกริด ต้องการหาจำนวนเซลล์สูงสุดที่ส่องสว่างได้โดยการวางหลอดอย่างเหมาะสม

ตัวอย่าง: h=4, w=4, grid={"#...", "....", "...#", "...."} ผลลัพธ์: 7

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

1. คำนวณอาร์เรย์ first (แนวนอน): สองครั้งซ้าย→ขวา และ ขวา→ซ้าย เก็บจำนวนเซลล์ว่างติดต่อกันในแนวนอน
2. คำนวณอาร์เรย์ second (แนวตั้ง): สองครั้งบน→ล่าง และ ล่าง→บน เก็บจำนวนเซลล์ว่างติดต่อกันในแนวตั้ง
3. สำหรับแต่ละเซลล์ (i,j) ผลรวม first[i][j] + second[i][j] คือจำนวนเซลล์ที่ส่องได้ (นับซ้ำเซลล์ตัวเอง) บวก 1 ได้คำตอบ
4. หาค่าสูงสุด

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

#include <bits/stdc++.h>
using namespace std;

int solve(int h, int w, vector<string> grid) {
    vector<vector<int>> first(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
        int count = 0;
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == '#') { count = 0; continue; }
            first[i][j] = count++;
        }
        int k = 0;
        for (int j = w-1; j >= 0; j--) {
            if (grid[i][j] == '#') { k = 0; continue; }
            k = max(k, first[i][j]);
            first[i][j] = k;
        }
    }
    vector<vector<int>> second(h, vector<int>(w));
    for (int j = 0; j < w; j++) {
        int count = 0;
        for (int i = 0; i < h; i++) {
            if (grid[i][j] == '#') { count = 0; continue; }
            second[i][j] = count++;
        }
        int k = 0;
        for (int i = h-1; i >= 0; i--) {
            if (grid[i][j] == '#') { k = 0; continue; }
            k = max(k, second[i][j]);
            second[i][j] = k;
        }
    }
    int result = 0;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            result = max(result, first[i][j] + second[i][j]);
    return result + 1;
}

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

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

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

Output: 7