โปรแกรมตรวจสอบจำนวนการใช้เข็มทิศเพื่อออกจากเขาวงกตเพียงพอใน Python

สมมุติว่าเรากำลังเล่นเกมที่เราติดอยู่ในเขาวงกต เราต้องหาทางออกจากเขาวงกต เขาวงกตสามารถนำเสนอเป็นเมทริกซ์ x m โดยที่ n คือจำนวนแถวและ m คือจำนวนคอลัมน์ แต่ละเซลล์/องค์ประกอบของเมทริกซ์มีสัญลักษณ์ 'O', 'D', 'S' หรือ '-' 'O' หมายความว่าเส้นทางถูกปิดกั้น 'D' คือทางออกจากเขาวงกต 'S' คือตำแหน่งเริ่มต้นของเรา และ '-' หมายความว่าเราสามารถเคลื่อนผ่านเส้นทางนั้นได้ เราสามารถเคลื่อนที่ได้อย่างอิสระผ่านเซลล์ที่มีเครื่องหมาย '-' ตอนนี้ เรายังมีเข็มทิศ ซึ่งเราสามารถหาทางออก (เซลล์ 'D') จากเขาวงกตได้ เมื่อเราต้องหาทิศทาง เราต้องใช้เข็มทิศ แต่เราสามารถใช้เข็มทิศได้มากที่สุด k ครั้ง เมื่อพิจารณาจากเขาวงกตเป็นเมทริกซ์และจำนวนครั้งที่เราใช้เข็มทิศได้ เราต้องค้นหาว่าเราจะออกจากเขาวงกตได้หรือเปล่าโดยใช้เข็มทิศหลายครั้งเท่านั้น หากเป็นไปได้ เราจะคืนค่าเป็น True หรือมิฉะนั้น เราจะคืนค่าเป็นเท็จ

ดังนั้นหากอินพุตเป็นเหมือนกริด =

n =4, m =11, k =3; แล้วผลลัพธ์จะเป็น True

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

• กำหนดฟังก์ชัน path_search() สิ่งนี้จะใช้ curr_pos, grid, total_rows, total_cols, k, รุ่นก่อน

  • x:=x ค่าของ curr_pos

  • y:=y ค่าของ curr_pos

  • ถ้า grid[x, y] เหมือนกับ "*" แล้ว

    • ถ้า k เท่ากับ 0 แล้ว

      • คืนค่า True

    • มิฉะนั้น

      • คืนค่าเท็จ

    • มิฉะนั้น

      • parent :=บรรพบุรุษ[curr_pos]

      • succ_pos :=รายการใหม่จากการคืนค่าของ succesor_positions(curr_pos, grid, total_rows, total_cols, parent)

      • use_compass :=True ถ้าขนาดของ succ_pos> 1

      • สำหรับแต่ละตำแหน่งใน succ_pos ทำ

        • รุ่นก่อน[ตำแหน่ง] :=curr_pos

        • ถ้า use_compass ไม่ใช่ศูนย์ แล้ว

          • path_search(ตำแหน่ง, ตาราง, total_rows, total_cols, k - 1, รุ่นก่อน)

        • มิฉะนั้น

          • path_search(ตำแหน่ง, ตาราง, total_rows, total_cols,k, รุ่นก่อน)

• กำหนดฟังก์ชัน succesor_positions() การดำเนินการนี้จะใช้เวลา curr_pos, grid, total_rows, total_cols, parent

  • x:=x ค่าของ curr_pos

  • y:=y ค่าของ curr_pos

  • succ_pos :=รายการใหม่

  • o ถ้า y> 0 แล้ว

    • ซ้าย :=x, y - 1

    • แทรกด้านซ้ายที่ท้าย succ_pos

  • ถ้า y

    • ขวา :=x, y + 1

    • แทรกทางขวาที่ท้าย succ_pos

  • ถ้า x> 0 แล้ว

    • ขึ้น :=x - 1, y

    • แทรกขึ้นที่ส่วนท้ายของ succ_pos

  • ถ้า x

    • ลง :=x + 1, y

    • แทรกลงที่ส่วนท้ายของ succ_pos

  • ถ้าสำหรับทุกตำแหน่งใน succ_pos, grid[position[0], pos[1]] คือ

  • ไม่เหมือนกับ "X" และ pos ไม่เหมือนกับ parent ดังนั้น −

    • ส่งคืนองค์ประกอบใน succ_pos ตามเงื่อนไข

ตอนนี้ดำเนินการดังต่อไปนี้ -

• curr_pos :=คู่ใหม่ที่ว่างเปล่า

• สำหรับแต่ละดัชนี i แถวรายการในตาราง ทำ

  • สำหรับแต่ละดัชนี j องค์ประกอบรายการในแถว ทำ

    • หากองค์ประกอบเหมือนกับ 'M' แล้ว

      • curr_pos :=คู่ใหม่ที่มี i, j

• ก่อนหน้า :=แผนที่ใหม่ที่ curr_pos :=Null เริ่มต้น

• path_search(curr_pos, กริด, n, m, k, รุ่นก่อน)

ซอร์สโค้ด (Python)

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

def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
   x, y = curr_pos
   if grid[x][y] == "D":
      if k == 0:
         print('True')
      else:
         print('False')
   else:
      parent = predecessor[curr_pos]
      succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
      use_compass = len(succ_pos) > 1
      for position in succ_pos:
         predecessor[position] = curr_pos
         if use_compass:
            path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
         else:
            path_search(position, grid, total_rows, total_cols, k, predecessor)

def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
   x, y = curr_pos
   succ_pos = []
   if y > 0:
      left = (x, y - 1)
      succ_pos.append(left)
   if y < total_cols - 1:
      right = (x, y + 1)
      succ_pos.append(right)
   if x > 0:
      up = (x - 1, y)
      succ_pos.append(up)
   if x < total_rows - 1:
      down = (x + 1, y)
      succ_pos.append(down)
   return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)

def solve(grid, n, m, k):
   curr_pos = ()
   for i, row in enumerate(grid):
      for j, element in enumerate(row):
         if element == 'S':
            curr_pos = (i, j)
   path_search(curr_pos, grid, n, m, k, predecessor = {curr_pos: None})

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]

solve(grid, 4, 11, 3)

อินพุต

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3

ผลลัพธ์

True