สมมติว่าเรามีเมทริกซ์ 2 มิติ โดยมีค่าน้อยดังนี้ -
-
0 หมายถึงเซลล์ว่าง
-
1 หมายถึงกำแพง
-
2 เป็นตัวแทนของบุคคล
ในที่นี้ บุคคลสามารถเดินได้สี่ทิศทาง (ขึ้น ลง ซ้าย และขวา) เราต้องหาห้องขังที่ไม่ใช่กำแพงเพื่อลดระยะการเดินทางทั้งหมดที่แต่ละคนต้องเดินไปให้น้อยที่สุดและในที่สุดก็หาระยะทางได้
ดังนั้นหากอินพุตเป็นแบบ
| 2 | 0 | 1 | 0 |
| 1 | 0 | 1 | 2 |
| 0 | 0 | 2 | 2 |
จากนั้นผลลัพธ์จะเป็น 7 เนื่องจากจุดนัดพบที่ดีที่สุดคือมุมล่างขวา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
twos :=แผนที่ใหม่ ราคา :=แผนที่ใหม่
-
สำหรับแต่ละดัชนี i และแถว r ในเมทริกซ์ ทำ
-
สำหรับแต่ละดัชนี j และค่า v ใน r ทำ
-
ถ้า v เท่ากับ 2 แล้ว
-
twos[i, j] :=[i, j, 0]
-
cost[i, j] :=สร้างเมทริกซ์ขนาด 2 มิติตามเมทริกซ์ที่กำหนดและเติมด้วยอนันต์
-
-
-
-
สำหรับแต่ละคู่ของค่าคีย์ (k, q) เป็นสอง ทำ
-
เห็นแล้ว :=ชุดใหม่
-
ในขณะที่ q ไม่ว่างให้ทำ
-
(i, j, cost) :=ลบองค์ประกอบแรกออกจาก q
-
ถ้า (i, j) อยู่ในนั้นแล้ว
-
ไปอ่านตอนต่อไป
-
-
เพิ่ม (i, j) เข้าไปแล้ว
-
ค่าใช้จ่าย[k, i, j] :=ต้นทุน
-
สำหรับแต่ละ (di, dj) ใน ((1, 0), (-1, 0), (0, 1), (0, −1)), ทำ
-
(ni, nj) :=(i + di, j + dj)
-
ถ้า ni และ nj อยู่ในช่วงของเมทริกซ์และเมทริกซ์[ni, nj] ไม่ใช่ 1 ดังนั้น
-
แทรก (ni, nj, ราคา + 1) ที่ส่วนท้ายของ q
-
-
-
-
-
ตอบ :=อนันต์
-
สำหรับฉันในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ทำ
-
สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ
-
cur_cost :=0
-
สำหรับแต่ละ arr ในรายการมูลค่าของต้นทุนทั้งหมด ทำ
-
cur_cost :=cur_cost + arr[i, j]
-
-
ans :=ขั้นต่ำของ ans และ cur_cost
-
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
คลาสโซลูชัน:def แก้ปัญหา(ตัวเอง, เมทริกซ์):twos ={} cost ={} for i, r in enumerate(matrix):สำหรับ j, v ใน enumerate(r):ถ้า v ==2:twos[ (i, j)] =[(i, j, 0)] ค่าใช้จ่าย[(i, j)] =[[1e9 สำหรับ _ ในเมทริกซ์[0]] สำหรับ _in matrix] สำหรับ k, q ใน twos.items() :seen =set() ในขณะที่ q:i, j, cost =q.pop(0) if (i, j) in seen:continue seen.add((i, j)) cost[k][i][j ] =ค่าใช้จ่ายสำหรับ di, dj ใน ((1, 0), (-1, 0), (0, 1), (0, -1)):ni, nj =i + di, j + dj if (ni>=0 และ nj>=0 และ ni อินพุต
เมทริกซ์ =[[2, 0, 1, 0],[1, 0, 1, 2],[0, 0, 2, 2]]
ผลลัพธ์
7
