ต้องใช้โปรแกรม C++ เพื่อค้นหาจำนวนการเจาะขั้นต่ำเพื่อให้บรรลุเป้าหมาย

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

ดังนั้นหากอินพุตเป็นแบบ

ผลลัพธ์จะเป็น 1 เพราะเราสามารถสร้างกริดได้ −

โดยการทำลายกล่องที่ทำเครื่องหมายไว้

ขั้นตอน

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

n := row count of matrix
m := column count of matrix
Define one 2D array dist of order (n + 1) x (m + 1)
Define one deque dq
insert ( 0, 0 ) at the beginning of dq
dist[0, 0] := 0
while (not dq is empty), do:
   v := first element of dq
   delete front element from dq
   for initialize i := 0, when i < 4, update (increase i by 1), do:
      x := dx[i] + v[0]
      y := dy[i] + v[1]
      if x >= 0 and x < n and y >= 0 and y < m, then:
         if matrix[x, y] is same as '.', then:
            if dist[x, y] > dist[v[0], v[1]], then:
               dist[x, y] := dist[v[0], v[1]]
               insert pair { x, y } at the beginning of dq
         Otherwise
            for initialize p := x - 1, when p <= x + 1, update (increase p by 1), do:
               for initialize q := y - 1, when q <= y + 1, update (increase q by 1), do:
                  if p >= 0 and p < n and q >= 0 and q < m, then:
                     if dist[p, q] > dist[v[0], v[1]] + 1, then:
                        dist[p, q] := dist[v[0], v[1]] + 1
                        insert pair { p, q } at the end of dq
return dist[n - 1, m - 1]

ตัวอย่าง

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

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

int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int solve(vector<vector<char>> matrix){
   int n = matrix.size();
   int m = matrix[0].size();
   vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
   deque<array<int, 2>> dq;
   dq.push_front({ 0, 0 });
   dist[0][0] = 0;
   while (!dq.empty()){
      auto v = dq.front();
      dq.pop_front();
      for (int i = 0; i < 4; i++){
         int x = dx[i] + v[0], y = dy[i] + v[1];
         if (x >= 0 && x < n && y >= 0 && y < m){
            if (matrix[x][y] == '.'){
               if (dist[x][y] > dist[v[0]][v[1]]){
                  dist[x][y] = dist[v[0]][v[1]];
                  dq.push_front({ x, y });
               }
            } else{
               for (int p = x - 1; p <= x + 1; p++){
                  for (int q = y - 1; q <= y + 1; q++){
                     if (p >= 0 && p < n && q >= 0 && q < m){
                        if (dist[p][q] > dist[v[0]][v[1]] + 1){
                           dist[p][q] = dist[v[0]][v[1]] + 1;
                           dq.push_back({ p, q });
                        }
                     }
                  }
               }
            }
         }
      }
   }
   return dist[n - 1][m - 1];
}
int main(){
   vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } };
   cout << solve(matrix) << endl;
}

อินพุต

{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, {
'.', '.', '#', '.', '.' } }

ผลลัพธ์

1