home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

เส้นทางที่ไม่ซ้ำ III ใน C++

สมมุติว่าเรามีตาราง 2 มิติ 1 อัน สี่เหลี่ยมมี 4 แบบ -

  • ในตารางที่ 1 เป็นจุดเริ่มต้น จะมีช่องเริ่มต้นเพียงหนึ่งช่องเท่านั้น

  • ในสี่เหลี่ยมจัตุรัสที่ 2 คือจุดสิ้นสุด จะมีช่องสี่เหลี่ยมสิ้นสุดเพียงช่องเดียว

  • ในช่อง 0 แทนช่องว่างแล้วเดินข้ามได้

  • ในสี่เหลี่ยมจัตุรัส -1 ถ้าสำหรับสิ่งกีดขวางที่เราเดินผ่านไม่ได้

เราต้องหาจำนวนการเดิน 4 ทิศทางจากจัตุรัสเริ่มต้นไปยังจัตุรัสสิ้นสุด ซึ่งเดินข้ามทุกช่องที่ไม่ขวางกั้นเพียงครั้งเดียว

ดังนั้นหากอินพุตเป็นเช่น −

1 0 0 0
0 0 0 0
1 0 2 -1

จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากเรามีสองเส้นทางนี้:(0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1),(1,0), (2,0), (2,1), (2,2) และ (0,0), (1,0), (2,0), (2 ,1), (1,1), (0,1), (0,2), (0,3), (1,3), (1,2), (2,2)

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

  • กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ตารางอาร์เรย์ 2 มิติ 1 อัน i, j, ex, ey, ว่างเปล่า

  • ถ้า i,j ไม่อยู่ในช่วงของกริดหรือกริด[i, j] เท่ากับ -1 ดังนั้น −

    • คืนค่า 0

  • ถ้า grid[i, j] เหมือนกับ 2 แล้ว

    • คืนค่าจริงเมื่อว่างเปล่าเป็น -1

  • x :=0

  • (ลดลงเหลือ 1)

  • กริด[i, j] :=-1

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

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

    • ny :=j + dir[k, 1]

    • x :=x + dfs(grid, nx, ny, ex, ey, ว่างเปล่า)

  • (ว่างเพิ่มขึ้น 1)

  • กริด[i, j] :=0

  • ผลตอบแทน x

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

  • ว่างเปล่า :=0

  • n :=จำนวนแถว m :=จำนวนคอลัมน์

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • สำหรับการเริ่มต้น j :=0 เมื่อ j

      • ถ้า grid[i, j] เท่ากับ 0 แล้ว

        • (ว่างเพิ่มขึ้น 1)

      • มิฉะนั้นเมื่อ grid[i, j] เหมือนกับ 1 แล้ว −

        • sx :=i, sy :=j

      • มิฉะนั้นเมื่อ grid[i, j] เหมือนกับ 2 แล้ว −

        • ตัวอย่าง :=i, ey :=j

  • ส่งคืน dfs(grid, sx, sy, ex, ey, ว่างเปล่า)

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

ตัวอย่าง

#include ใช้เนมสเปซ std;int dir[4][2] ={{1,0},{-1,0},{0,1},{0,-1 }};คลาสโซลูชัน { สาธารณะ:int dfs(vector>&grid, int i, int j, int ex, int ey, int ว่างเปล่า){ if (i>=grid.size() || i <0 || j>=grid[0].size() || j <0 || grid[i][j] ==-1) คืนค่า 0; if (grid[i][j] ==2) { return ว่างเปล่า ==-1; } int x =0; ว่างเปล่า--; กริด[i][j] =-1; สำหรับ (int k =0; k <4; k++) { int nx =i + dir[k][0]; int ny =j + dir[k][1]; x +=dfs(grid, nx, ny, ex, ey, ว่างเปล่า); } ว่างเปล่า++; ตาราง[i][j] =0; ผลตอบแทน x; } int uniquePathsIII(vector>&grid){ int empty =0; int sx, sy, อดีต, ey; int n =grid.size(); int m =กริด[0].size(); for (int i =0; i > v ={{1,0,0,0},{0,0,0,0},{0,0,2,-1}}; ศาล <<(ob.uniquePathsIII(v));}

อินพุต

<ล่วงหน้า>{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}

ผลลัพธ์

2