Đường dẫn ngắn nhất trong ma trận nhị phân trong C ++

Giả sử chúng ta có một lưới ô vuông N x N, ở đó mỗi ô trống (0) hoặc bị chặn (1). Một đường dẫn rõ ràng từ trên cùng bên trái đến dưới cùng bên phải có độ dài k nếu và chỉ khi nó bao gồm các ô C_1, C_2, ..., C_k sao cho -

• Các ô liền kề C_i và C_ {i + 1} được kết nối 8 hướng (Vì vậy, chúng khác nhau và có chung một cạnh hoặc góc)

• C_1 ở vị trí (0, 0)

• C_k ở vị trí (N-1, N-1)

• Nếu C_i nằm ở (r, c), thì lưới [r, c] trống hoặc chứa 0

Chúng ta phải tìm độ dài của con đường rõ ràng ngắn nhất như vậy từ trên cùng bên trái đến dưới cùng bên phải. Nếu không có đường dẫn như vậy, hãy trả về -1.

Ví dụ:nếu lưới giống như -

Các ô màu cam sẽ là đường dẫn. Chiều dài là 4

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

• Xác định mảng hướng, mảng này sẽ chứa 8 cặp để di chuyển 8 hướng khác nhau. Vì vậy, mảng này giống như [[1,1], [1, -1], [-1,1], [1,0], [0,1], [-1, -1], [0, - 1], [-1,0]]

• Phần chính sẽ lấy lưới làm đầu vào, phần này sẽ hoạt động như bên dưới -

• xác định hàng đợi các điểm, q, n:=số hàng

• nếu lưới [0, 0] là 0, thì tạo một điểm mới p (0, 0, 1), chèn p vào q và tạo lưới [0, 0]:=1

• trong khi q không trống

  • curr:=điểm phía trước từ q, xóa điểm phía trước khỏi q

  • x:=x giá trị của curr, y:=y giá trị của curr, c:=c giá trị của curr

  • nếu x =n - 1 và y =n - 1, thì trả về c

  • tăng c lên 1

  • cho tôi trong phạm vi từ 0 đến 7

    • X:=x + d [i, 0], Y:=y + d [i, 1]

    • nếu X trong phạm vi 0 và n và y trong phạm vi 0 và n và lưới [X, Y] là 0, thì

      • lưới [X, Y]:=1

      • chèn một điểm mới p (X, Y, c) vào q

• trả về -1

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1},
{0, -1}, {-1, 0}};
struct point{
   int x, y, c;
   point(int a, int b, int z){
      x = a;
      y = b;
      c = z;
   }
};
class Solution {
   public:
   int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
      queue <point> q;
      int n = grid.size();
      if(!grid[0][0]){
         q.push(point(0, 0, 1));
         grid[0][0] = 1;
      }
      while(!q.empty()){
         point curr = q.front();
         q.pop();
         int x = curr.x;
         int y = curr.y;
         int c = curr.c;
         if(x == n-1 && y == n-1)return c;
            c++;
         for(int i = 0; i < 8; i++){
            int X = x + d[i][0];
            int Y = y + d[i][1];
            if(X >= 0 && X < n && Y >= 0 && Y < n &&
            !grid[X][Y]){
               grid[X][Y] = 1;
               q.push(point(X, Y, c));
            }
         }
      }
      return -1;
   }
};
main(){
   vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
   Solution ob;
   cout << (ob.shortestPathBinaryMatrix(v));
}

Đầu vào

[[0,0,0],[1,1,0],[1,1,0]]

Đầu ra

4