โปรแกรม C++ ค้นหาจำนวนเซลล์ที่จะบล็อกในตารางเพื่อสร้างเส้นทาง

สมมติว่ามีตารางขนาด h * w มีหุ่นยนต์อยู่ในตำแหน่งเซลล์ (0, 0) และต้องไปที่ตำแหน่ง (h - 1, w - 1) มีเซลล์สองประเภทในกริด คือ บล็อกและยกเลิกการบล็อก หุ่นยนต์สามารถผ่านเซลล์ที่ไม่ถูกบล็อกได้ แต่ไม่สามารถผ่านเซลล์ที่ถูกบล็อกได้ หุ่นยนต์สามารถไปได้สี่ทิศทาง มันสามารถไปทางซ้าย ขวา ขึ้นและลง แต่หุ่นยนต์อาจไปในทิศทางใดก็ได้จากเซลล์หนึ่งไปยังอีกเซลล์หนึ่ง (โดยไม่สนใจเซลล์ก่อนหน้าที่มันอยู่) ดังนั้นเราจึงต้องทำเพียงเส้นทางเดียวและปิดกั้นเซลล์อื่นๆ ทั้งหมดที่ไม่ได้อยู่ในเส้นทางนั้น เราต้องหาและส่งคืนจำนวนเซลล์ที่เราต้องบล็อกเพื่อสร้างเส้นทางเดียวสำหรับหุ่นยนต์จาก (0, 0) ถึง (h - 1, w - 1) และหากไม่มีเส้นทางที่เป็นไปได้ เราจะคืนค่า -1

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

เราต้องบล็อกเพียงสองเซลล์เพื่อสร้างเส้นทางเดียวจาก (0, 0) ถึง (3, 3)

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

Define one 2D array dp
dp[0, 0] := 0
Define an array moves containing pairs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
Define one queue q
insert pair (0, 0) at the end of q
while (not q is empty), do:
   p := first element of q
   delete first element from q
   for initialize i := 0, when i < 4, update (increase i by 1), do:
      row := first value of p + first value of moves[i]
      col := second value of p + second value of moves[i]
      if row < 0 or row > h - 1 or col < 0 or col > w - 1, then:
         Ignore following part, skip to the next iteration
      if grid[row, col] is same as '#', then:
         Ignore following part, skip to the next iteration
      if dp[first value of p, second value of p] + 1 < dp[row, col], then:
         dp[row, col] := dp[first value of p, second value of p] + 1
         insert pair(row, col) into q
if dp[h - 1, w - 1] is same as 2500, then:
   return -1
count := 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:
      if grid[i, j] is same as '.', then:
         (increase count by 1)
return count - (dp[h - 1, w - 1] + 1)

ตัวอย่าง

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

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

int solve(int h, int w, vector<string> grid){
   vector<vector<int>> dp(h, vector<int>(w, 2500));
   dp[0][0] = 0;
   vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
   queue<pair<int, int>> q;
   q.push(make_pair(0, 0));
   while (!q.empty()) {
      auto p = q.front();
      q.pop();
      for (int i = 0; i < 4; i++) {
         int row = p.first + moves[i].first;
         int col = p.second + moves[i].second;
         if (row < 0 || row > h - 1 || col < 0 || col > w - 1) continue;
         if (grid[row][col] == '#') 
            continue;
         if (dp[p.first][p.second] + 1 < dp[row][col]) {
            dp[row][col] = dp[p.first][p.second] + 1; q.push(make_pair(row, col));
         }
      }
   }
   if (dp[h - 1][w - 1] == 2500) {
      return -1;
   }
   int count = 0;
   for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
         if (grid[i][j] == '.') count++;
      }
   }
   return count - (dp[h - 1][w - 1] + 1);
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"..#.", "#.#.", "#.##", "#..."};
   cout<< solve(h, w, grid);
   return 0;
}

อินพุต

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

ผลลัพธ์

2