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

สมมติว่าเราได้รับตารางขนาด h * w เซลล์ในตารางอาจมีหลอดไฟหรือสิ่งกีดขวางก็ได้ เซลล์หลอดไฟส่องสว่างเซลล์ทางด้านขวา ซ้าย ขึ้นและลง และแสงสามารถส่องผ่านเซลล์ได้ เว้นแต่เซลล์สิ่งกีดขวางจะปิดกั้นแสง เซลล์ของสิ่งกีดขวางไม่สามารถส่องสว่างได้ และจะปิดกั้นแสงจากเซลล์หลอดไฟไม่ให้ไปถึงเซลล์อื่น เราได้รับตารางในอาร์เรย์ของสตริง โดยที่ '#' แทนสิ่งกีดขวางและ '.' หมายถึงเซลล์ว่าง เรามีหลอดไฟเพียงหลอดเดียว และเราต้องหาจำนวนเซลล์สูงสุดที่เราสามารถให้แสงสว่างเพื่อวางหลอดไฟในตารางได้อย่างเหมาะสมที่สุด

ดังนั้น หากอินพุตเป็น h =4, w =4, grid ={"#...", "....", "...#", "...."} ก็จะได้ผลลัพธ์ จะเท่ากับ 7.

จากภาพ เราจะเห็นเซลล์เรืองแสงในตาราง

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

Define one 2D array first
for initialize i := 0, when i < h, update (increase i by 1), do:
   count := 0
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if grid[i, j] is same as '#', then:
         count := 0
         Ignore following part, skip to the next iteration
      else:
         first[i, j] := count
         (increase count by 1)
   k := 0
   for initialize j := w - 1, when j >= 0, update (decrease j by 1), do:
      if grid[i, j] is same as '#', then:
         k := 0
        Ignore following part, skip to the next iteration
     else:
        k := maximum of k and first[i, j]
        first[i, j] := k
Define one 2D array second
for initialize j := 0, when j < w, update (increase j by 1), do:
   count := 0
   for initialize i := 0, when i < h, update (increase i by 1), do:
      if grid[i, j] is same as '#', then:
         count := 0
         Ignore following part, skip to the next iteration
      else:
         second[i, j] := count
         (increase count by 1)
k := 0
for initialize i := h - 1, when i >= 0, update (decrease i by 1), do:
   if grid[i, j] is same as '#', then:
      k := 0
      Ignore following part, skip to the next iteration
   else:
      k := maximum of k and second[i, j]
      second[i, j] := k
result := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      result := maximum of result and first[i, j] + second[i, j]
return result + 1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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;
         } else {
            first[i][j] = count;
            count++;
         }
      }
      int k = 0;
      for(int j = w-1; j >= 0; j--) {
         if(grid[i][j] == '#') {
            k = 0;
            continue;
         } else {
            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;
         } else {
            second[i][j] = count;
            count++;
         }
      }
      int k = 0;
      for(int i = h-1; i >= 0; i--) {
         if(grid[i][j] == '#') {
            k = 0;
            continue;
         } else {
            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;
}

อินพุต

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