Chương trình C ++ để tìm số lượng cú đấm tối thiểu là cần thiết để tạo đường đạt được mục tiêu

Giả sử chúng ta có một ma trận chứa H hàng và W cột. Các ô giữ '.' hoặc '#'. Dấu chấm '.' cho biết không gian có thể chuyển và '#' cho biết khối. Amal sẽ đi từ nhà của mình đến một khu chợ. Nhà của anh ta ở phòng giam ở góc trên bên trái, và chợ ở góc dưới cùng bên phải. Amal có thể di chuyển một ô lên, xuống, sang trái hoặc phải đến một ô có thể chuyển được. Anh ta không thể rời khỏi thị trấn. Anh ta cũng không thể vào một ô bị chặn. Tuy nhiên, sức mạnh thể chất của anh ta cho phép anh ta phá hủy tất cả các khối trong một khu vực hình vuông với các ô 2 × 2 do anh lựa chọn chỉ bằng một cú đấm, làm cho các ô này có thể vượt qua được. Chúng tôi phải tìm ra số lượng cú đấm tối thiểu cần thiết để Amal tiếp cận thị trường.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 1, vì chúng ta có thể làm cho lưới giống như -

bằng cách phá hủy các hộp đã đánh dấu

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

1