เส้นทางที่สั้นที่สุดในตารางพร้อมการขจัดอุปสรรคใน C++

สมมติว่าเรามีตารางขนาด mxn โดยที่แต่ละเซลล์มี 0 หรือ 1 0 เซลล์ว่างเปล่าและ 1 ถูกบล็อก ในขั้นตอนเดียว เราสามารถเลื่อนขึ้น ลง ซ้าย หรือขวาจากและไปยังเซลล์ว่างได้ เราต้องหาจำนวนขั้นขั้นต่ำที่จะเดินจากเซลล์มุมบนซ้าย (0, 0) ไปยังเซลล์มุมล่างขวา (m-1, n-1) เนื่องจากเราสามารถกำจัดสิ่งกีดขวางได้มากถึง k อัน หากไม่มีวิธีดังกล่าว ให้คืนค่า -1

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

และ k คือ 1 ผลลัพธ์จะเป็น 6 เนื่องจากเส้นทางที่สั้นที่สุดโดยไม่กำจัดสิ่งกีดขวางใด ๆ คือ 10 เส้นทางที่สั้นที่สุดที่มีการกำจัดสิ่งกีดขวางที่ตำแหน่ง (3,2) จะเป็น 6 เส้นทางดังกล่าวจะเป็น (0,0) ถึง (0,1) ถึง (0,2) ถึง (1,2) ถึง (2,2) ถึง (3,2) ถึง (4,2)

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

• กำหนดฟังก์ชัน ok() ซึ่งจะตรวจสอบว่า x และ y อยู่ในช่วง r และ c หรือไม่

• กำหนดอาร์เรย์ dp ขนาด 50 x 50 x 2000

• กำหนดโครงสร้างข้อมูลหนึ่งโครงสร้างที่มี x, y, k และความยาว

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• เติม dp ด้วย inf

• r :=จำนวนแถว, c :=จำนวนคอลัมน์

• กำหนดหนึ่งคิว q

• สร้างวัตถุข้อมูลที่เรียกว่ารูทด้วย (x =0, y =0, k, length =0)

• แทรกรูทลงใน q

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • โหนด :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • x :=node.x, y :=node.y, k :=node.k, length :=node.length

  • ถ้า x เหมือนกับ r - 1 และ y เหมือนกับ c - 1 แล้ว −

    • ความยาวกลับ

  • (เพิ่มความยาว 1)

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <4 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

    • nx :=x + dir[i, 0]

    • ny :=y + dir[i, 1]

    • ถ้า nx เหมือนกับ r - 1 และ ny เหมือนกับ c - 1 แล้ว −

      • ความยาวกลับ

    • ถ้า ok(nx, ny, r, c) เป็นจริง −

      • ถ้า grid[nx, ny] เท่ากับ 0 แล้ว −

        • ถ้าความยาว

          • แทรกวัตถุข้อมูลใหม่ด้วย (x =nx, y =ny, k, length) ลงใน q

          • dp[nx, ny, k] :=ความยาว

      • มิฉะนั้น

        • ถ้า k> 0 และความยาว

          • แทรกวัตถุข้อมูลใหม่ด้วย (x =nx, y =ny, k =k - 1,length) ลงใน q

          • dp[nx, ny, k] :=ความยาว

• กลับ -1

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

ตัวอย่าง

#include ใช้เนมสเปซ std;int dir [4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1 }};int dp[50][50][2000];จัดโครงสร้างข้อมูล{ int x, y, k, ความยาว; ข้อมูล (int a, int b, int c, int d){ x =a; y =ข; k =ค; ความยาว =ง; }};คลาสโซลูชัน { สาธารณะ:void pre(){ สำหรับ (int i =0; i <50; i++) { สำหรับ (int j =0; j <50; j++) { สำหรับ (int k =0; k <2000; k++) { dp[i][j][k] =INT_MAX; } } } } bool ตกลง (int x, int y, int r, int c){ return (x =0 &&y>=0); } int shortestPath(vector>&grid, int k){ pre(); int r =grid.size(); int c =กริด[0].size(); คิว<ข้อมูล> q; รากข้อมูล(0, 0, k, 0); q.push(ราก); ในขณะที่ (!q.empty()) { โหนดข้อมูล =q.front(); q.ป๊อป(); int x =node.x; int y =node.y; int k =node.k; ความยาว int =node.length; ถ้า (x ==r - 1 &&y ==c - 1) ความยาวของผลตอบแทน; ความยาว++; สำหรับ (int i =0; i <4; i++) { int nx =x + dir[i][0]; int ny =y + dir[i][1]; if (nx ==r - 1 &&ny ==c - 1) return length; if (ok(nx, ny, r, c)) { if (grid[nx][ny] ==0) { if (length  0 &&ความยาว > v ={{0,0,0},{1,1,0},{0,0,0},{0,1,1}, {0,0,0}}; ศาล <<(ob.shortestPath(v, 1));}

อินพุต

ผลลัพธ์

6