โปรแกรม C++ หาจำนวนเซลล์เรืองแสงในตาราง

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

ดังนั้น หากอินพุตเป็น h =4, w =4, bulb ={{1, 1}, {2, 2}, {3, 3}}, สิ่งกีดขวาง ={{0, 0}, {2, 3 }} แล้วผลลัพธ์จะเป็น 13

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

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

bulbSize := size of bulb
blockSize := size of obstacle
Define one 2D array grid
for initialize i := 0, when i < bulbSize, update (increase i by 1), do:
   x := first value of bulb[i]
   y := second value of bulb[i]
   grid[x, y] := 1
for initialize i := 0, when i < blockSize, update (increase i by 1), do:
   x := first value of obstacle[i]
   y := first value of obstacle[i]
   grid[x, y] := 2
result := h * w
Define one 2D array check
for initialize i := 0, when i < h, update (increase i by 1), do:
   gd := 0
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if grid[i, j] is same as 2, then:
         gd := 0
      if grid[i, j] is same as 1, then:
         gd := 1
      check[i, j] := check[i, j] OR gd
   gd := 0
   for initialize j := w - 1, when j >= 0, update (decrease j by 1), do:
      if grid[i, j] is same as 2, then:
         gd := 0
      if grid[i, j] is same as 1, then:
         gd := 1
      check[i, j] := check[i, j] OR gd
for initialize j := 0, when j < w, update (increase j by 1), do:
   k := 0
   for initialize i := 0, when i < h, update (increase i by 1), do:
      if grid[i, j] is same as 2, then:
         k := 0
      if grid[i, j] is same as 1, then:
         k := 1
      check[i, j] := check[i, j] OR k
   k := 0
   for initialize i := h - 1, when i >= 0, update (decrease i by 1), do:
      if grid[i, j] is same as 2, then:
         k := 0
      if grid[i, j] is same as 1, then:
         k := 1
     check[i, j] := check[i, j] OR k
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 := result - NOT(check[i, j])
return result

ตัวอย่าง

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

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

อินพุต

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

ผลลัพธ์

13