สมมติว่าเรามีกระดาน 3x3 ซึ่งตัวเลขทั้งหมดอยู่ในช่วง 0 ถึง 8 และไม่มีตัวเลขซ้ำ ตอนนี้ เราสามารถสลับ 0 กับหนึ่งใน 4 เพื่อนบ้านของมันได้ และเรากำลังพยายามแก้ปัญหาเพื่อให้ได้ลำดับที่จัดเรียงทั้งหมด เราต้องหาจำนวนขั้นตอนขั้นต่ำที่จำเป็นเพื่อให้บรรลุเป้าหมาย
ดังนั้นหากอินพุตเป็นแบบ
| 3 | 1 | 2 |
| 4 | 7 | 5 |
| 6 | 8 | 0 |
แล้วผลลัพธ์จะเป็น 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน find_next() นี่จะใช้โหนด
- ย้าย :=แผนที่กำหนดการเคลื่อนไหวเป็นรายการที่สอดคล้องกับแต่ละค่า {0:[1, 3],1:[0, 2, 4],2:[1, 5],3:[0, 4 , 6],4:[1, 3, 5, 7],5:[2, 4, 8],6:[3, 7],7:[4, 6, 8],8:[5, 7 ],}
- ผลลัพธ์ :=รายการใหม่
- pos_0 :=ค่าแรกของโหนด
- สำหรับการเคลื่อนไหวแต่ละครั้ง[pos_0] ทำ
- new_node :=รายการใหม่จากโหนด
- สลับ new_node[move] และ new_node[pos_0]
- แทรก tuple ใหม่จาก new_node ที่ส่วนท้ายของผลลัพธ์
- แสดงผลลัพธ์
- กำหนดฟังก์ชัน get_paths() นี่จะใช้เวลา dict
- cnt :=0
- ทำสิ่งต่อไปนี้อย่างไม่สิ้นสุด ทำ
- current_nodes :=รายการที่ค่าเหมือนกับ cnt
- ถ้าขนาดของ current_nodes เท่ากับ 0 แล้ว
- คืน -1
- สำหรับแต่ละโหนดใน current_nodes ทำ
- next_moves :=find_next(โหนด)
- สำหรับการเคลื่อนไหวแต่ละครั้งใน next_moves ทำ
- หากไม่มีการเคลื่อนไหวใน dict แล้ว
- dict[move] :=cnt + 1
- หากการเคลื่อนไหวเหมือนกับ (0, 1, 2, 3, 4, 5, 6, 7, 8) แล้ว
- ส่งคืน cnt + 1
- cnt :=cnt + 1
- หากไม่มีการเคลื่อนไหวใน dict แล้ว
- จากวิธีหลัก ให้ทำดังนี้:
- dict :=แผนที่ใหม่ :=รายการใหม่
- สำหรับ i ในช่วง 0 ถึงแถวของบอร์ด ทำ
- แบน :=แบน + กระดาน[i]
- แผ่ :=สำเนาของแฟบ
- ดิก[แผ่] :=0
- ถ้าทำให้แบนเหมือนกับ (0, 1, 2, 3, 4, 5, 6, 7, 8) แล้ว
- คืน 0
- ส่งคืน get_paths(dict)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def solve(self, board):
dict = {}
flatten = []
for i in range(len(board)):
flatten += board[i]
flatten = tuple(flatten)
dict[flatten] = 0
if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return 0
return self.get_paths(dict)
def get_paths(self, dict):
cnt = 0
while True:
current_nodes = [x for x in dict if dict[x] == cnt]
if len(current_nodes) == 0:
return -1
for node in current_nodes:
next_moves = self.find_next(node)
for move in next_moves:
if move not in dict:
dict[move] = cnt + 1
if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return cnt + 1
cnt += 1
def find_next(self, node):
moves = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4, 6],
4: [1, 3, 5, 7],
5: [2, 4, 8],
6: [3, 7],
7: [4, 6, 8],
8: [5, 7],
}
results = []
pos_0 = node.index(0)
for move in moves[pos_0]:
new_node = list(node)
new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
results.append(tuple(new_node))
return results
ob = Solution()
matrix = [
[3, 1, 2],
[4, 7, 5],
[6, 8, 0]
]
print(ob.solve(matrix)) อินพุต
matrix = [ [3, 1, 2], [4, 7, 5], [6, 8, 0] ]
ผลลัพธ์
4
