Chương trình C ++ để tìm ra số lần di chuyển tối đa để đến một ô chưa bị chặn đến một ô chưa bị chặn khác trong lưới

Giả sử, chúng ta được cung cấp một lưới có kích thước h * w chứa hai loại ô, bị chặn và không bị chặn. Các ô bị chặn có nghĩa là các ô không thể truy cập được và việc bỏ chặn có nghĩa là các ô đó có thể truy cập được. Chúng tôi biểu diễn lưới trong một mảng 2D trong đó các ô bị chặn được cho là '#' và các ô không bị chặn được cho là '.'. Bây giờ, chúng ta phải tiếp cận từ một ô không bị chặn đến một ô không bị chặn khác trong lưới. Chúng tôi chỉ có thể thực hiện hai động tác, chúng tôi có thể đi dọc hoặc chúng tôi có thể đi ngang. Chúng ta không thể di chuyển theo đường chéo. Chúng ta phải ghi nhớ rằng, chúng ta chỉ có thể di chuyển đến các ô không bị chặn. Vì vậy, chúng tôi phải tìm ra số lần di chuyển tối đa cần thiết để đến một ô bỏ chặn từ một ô không bị chặn khác trong lưới.

Vì vậy, nếu đầu vào là h =4, w =4, grid ={".. #.", "#. #.", ".. ##", "###."}, Thì đầu ra sẽ là 4.

Từ ô (0,0), cần tối đa 4 lần di chuyển để đến ô (2, 0).

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

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

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

Đầu vào

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

Đầu ra

4