โปรแกรม C++ เพื่อค้นหาจำนวนการเคลื่อนไหวสูงสุดในการเข้าถึงเซลล์ที่ไม่ถูกบล็อกไปยังเซลล์อื่นที่ไม่ถูกบล็อกในตาราง

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

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

จากเซลล์ (0,0) ต้องย้ายสูงสุด 4 ครั้งเพื่อไปยังเซลล์ (2, 0)

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

Define an array xdir of size: 4 := {1, 0, - 1, 0}
Define an array ydir of size: 4 := {0, 1, 0, - 1}
Define one 2D array dist
Define one 2D array reset
res := 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:
      dist := reset
      if grid[i, j] is same as '.', then:
         dist[i, j] := 0
         Define one queue q containing integer pairs
         insert make_pair(i, j) into q
         while (not q is empty), do:
            x := first element of the leftmost element in the q
            y := second element of the leftmost element in the q
            res := maximum of (dist[x, y] and res)
            delete leftmost element from q
            for initialize k := 0, when k < 4, update (increase k by 1), do:
               px := x + xdir[k]
               py := y + ydir[k]
               if px >= 0 and px < h and py >= 0 and py < w, then:
                  if grid[px, py] is same as '.', then:
                     if dist[px, py] is same as -1, then:
                        dist[px, py] := dist[x, y] + 1
                        insert pair(px, py) into q
return res

ตัวอย่าง

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

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

int solve(int h, int w, vector<string> grid){
   int xdir[4] = {1, 0, -1, 0};
   int ydir[4] = {0, 1, 0, -1};
   vector<vector<int>> dist(h, vector<int>(w, -1));
   vector<vector<int>> reset(h, vector<int>(w, -1));
   int res = 0;
   for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
          dist = reset;
          if(grid[i][j] == '.'){
             dist[i][j] = 0;
             queue<pair<int,int>> q;
             q.push(make_pair(i, j));
             while(!q.empty()){
                int x = q.front().first;
                int y = q.front().second;
                res = max(dist[x][y], res);
                q.pop();
                for(int k = 0; k < 4; k++){
                   int px = x + xdir[k];
                   int py = y + ydir[k];
                   if(px >= 0 && px < h && py >= 0 && py < w){
                      if(grid[px][py] == '.'){
                         if(dist[px][py] == -1){
                            dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py));
                         }
                      }
                   }
                }
             }
         }
      }
   }
   return res;
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"..#.", "#.#.", "..##", "###."};
   cout << solve(h, w, grid);
   return 0;
}

อินพุต

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

ผลลัพธ์

4