เส้นทางที่สั้นที่สุดในเมทริกซ์ไบนารีใน C ++

สมมติว่าเรามีตารางสี่เหลี่ยมจัตุรัส N คูณ N โดยที่แต่ละเซลล์จะว่าง (0) หรือถูกบล็อก (1) เส้นทางที่ชัดเจนจากบนซ้ายไปล่างขวามีความยาว k ก็ต่อเมื่อมันประกอบด้วยเซลล์ C_1, C_2, ..., C_k เช่นนั้น -

• เซลล์ที่อยู่ติดกัน C_i และ C_{i+1} เชื่อมต่อกัน 8 ทิศทาง (ดังนั้นจึงต่างกันและใช้ขอบหรือมุมร่วมกัน)

• C_1 อยู่ที่ตำแหน่ง (0, 0)

• C_k อยู่ที่ตำแหน่ง (N-1, N-1)

• หาก C_i อยู่ที่ (r, c) ดังนั้น grid[r, c] จะว่างเปล่าหรือมี 0

เราต้องหาความยาวของเส้นทางที่ชัดเจนที่สุดจากซ้ายบนไปล่างขวา หากไม่มีเส้นทางดังกล่าว ให้คืนค่า -1

ตัวอย่างเช่น ถ้าเส้นกริดเป็นแบบ −

เซลล์สีส้มจะเป็นเส้นทาง ความยาว 4

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

• กำหนดอาร์เรย์ทิศทาง ซึ่งจะถือ 8 คู่เพื่อย้าย 8 ทิศทางที่แตกต่างกัน อาร์เรย์นี้จึงเป็นแบบ [[1,1], [1,-1], [-1,1], [1,0], [0,1], [-1,-1], [0,- 1], [-1,0]]

• ส่วนหลักจะใช้กริดเป็นอินพุต ซึ่งจะทำหน้าที่ดังต่อไปนี้ -

• กำหนดคิวของจุด q, n:=จำนวนแถว

• ถ้า grid[0, 0] เป็น 0, ให้สร้างจุดใหม่ p(0, 0, 1), แทรก p ลงใน q และสร้าง grid[0, 0] :=1

• ในขณะที่ q ไม่ว่างเปล่า

  • curr :=front point จาก q, ลบ front point จาก q

  • x :=x ค่าของสกุลเงิน y :=y ค่าของสกุลเงิน c :=ค่าของสกุลเงิน c

  • ถ้า x =n – 1 และ y =n – 1 ให้คืนค่า c

  • เพิ่มคขึ้น 1

  • สำหรับผมอยู่ในช่วง 0 ถึง 7

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

    • ถ้า X ในช่วง 0 และ n และ y ในช่วง 0 และ n และกริด[X, Y] เป็น 0 ดังนั้น

      • ตาราง[X, Y] :=1

      • แทรกจุดใหม่ p (X, Y, c) ลงใน q

• กลับ -1

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

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

4