ค้นหาระยะทางที่สั้นที่สุดจากยามใน Bankin Python

สมมติว่าเรามีเมทริกซ์ที่เต็มไปด้วยตัวอักษรสามตัว 'O', 'G' และ 'W' โดยที่ 'O' เป็นตัวแทนของพื้นที่เปิดโล่ง 'G' เป็นตัวแทนของยามและ 'W' เป็นตัวแทนของกำแพงในธนาคาร เราต้องแทนที่ตัว O ทั้งหมดในเมทริกซ์ด้วยระยะห่างที่สั้นที่สุดจากการ์ดเพียงตัวเดียว เราไม่สามารถทะลุผ่านกำแพงใดๆ ได้ ในการ์ดเมทริกซ์เอาต์พุตจะถูกแทนที่ด้วย 0 และกำแพงจะถูกแทนที่ด้วย -1

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

ผลลัพธ์จะเป็น

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

• ม :=5

• ไม่มี :=5

• dir_row :=[-1, 0, 1, 0]

• dir_col :=[0, 1, 0, -1]

• กำหนดฟังก์ชัน is_ok() นี่จะใช้เวลา i, j

• ถ้า (i อยู่ในช่วง 0 และ M) หรือ (j ในช่วง 0 และ j N) แล้ว

  • คืนค่าเท็จ

• คืนค่า True

• กำหนดฟังก์ชัน isSafe() นี่จะใช้เวลา i, j,matrix, ผลลัพธ์

• ถ้าเมทริกซ์[i, j] ไม่ใช่ 'O' หรือผลลัพธ์[i, j] ไม่ใช่ -1 แล้ว

  • คืนค่าเท็จ

• คืนค่า True

• กำหนดฟังก์ชัน calc_dist() ซึ่งจะใช้เมทริกซ์

• ผลลัพธ์ :=สร้างเมทริกซ์ของคำสั่ง M x N และเติมด้วย -1

• กำหนดคิวสองสิ้นสุด q

• สำหรับผมอยู่ในช่วง 0 ถึง M ทำ

  • สำหรับ j ในช่วง 0 ถึง N ให้ทำ

    • ผลลัพธ์[i, j] :=-1

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

      • ตำแหน่ง :=[i, j, 0]

      • แทรก pos ที่ด้านซ้ายของ q

      • ผลลัพธ์[i, j] :=0

• ในขณะที่ขนาดของ q> 0 ไม่ใช่ศูนย์ ให้ทำ

  • curr :=ลบองค์ประกอบสุดท้ายออกจาก q

  • x, y, dist :=curr[0], curr[1], curr[2]

  • สำหรับผมอยู่ในช่วง 0 ถึง 3 ทำ

    • ถ้า is_ok(x + dir_row[i], y + dir_col[i]) ไม่เป็นศูนย์และ isSafe(x + dir_row[i], y + dir_col[i], matrix, result) ไม่เป็นศูนย์ ดังนั้น

      • ผลลัพธ์[x + dir_row[i], y + dir_col[i]] :=dist + 1

      • ตำแหน่ง :=[x + dir_row[i], y + dir_col[i], dist + 1]

      • แทรก pos ที่ด้านซ้ายของ q

• สำหรับผมอยู่ในช่วง 0 ถึง M ทำ

  • สำหรับ j ในช่วง 0 ถึง N ให้ทำ

    • แสดงผล[i, j]

  • ไปที่บรรทัดถัดไป

ตัวอย่าง

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

from collections import deque as queue
M = 5
N = 5
dir_row = [-1, 0, 1, 0]
dir_col = [0, 1, 0, -1]
def is_ok(i, j):
   if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)):
      return False
   return True
def isSafe(i, j,matrix, result):
   if (matrix[i][j] != 'O' or result[i][j] != -1):
      return False
   return True
def calculate_dist(matrix):
   result = [[ -1 for i in range(N)]for i in range(M)]
   q = queue()
   for i in range(M):
      for j in range(N):
         result[i][j] = -1
         if (matrix[i][j] == 'G'):
            pos = [i, j, 0]
            q.appendleft(pos)
            result[i][j] = 0
   while (len(q) > 0):
      curr = q.pop()
      x, y, dist = curr[0], curr[1], curr[2]
   for i in range(4):
      if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1
      pos = [x + dir_row[i], y + dir_col[i], dist + 1]
      q.appendleft(pos)
   for i in range(M):
      for j in range(N):
         if result[i][j] > 0:
            print(result[i][j], end=" ")
         else:
            print(result[i][j],end=" ")
      print()

matrix = [['O', 'O', 'O', 'O', 'G'],
   ['O', 'O', 'O', 'W', 'O'],
   ['O', 'W', 'O', 'O', 'O'],
   ['G', 'W', 'W', 'W', 'O'],
   ['O', 'O', 'O', 'O', 'G']]

calculate_dist(matrix)

อินพุต

[['O', 'O', 'O', 'O', 'G'],
['O', 'O', 'O', 'W', 'O'],
['O', 'W', 'O', 'O', 'O'],
['G', 'W', 'W', 'W', 'O'],
['O', 'O', 'O', 'O', 'G']]

ผลลัพธ์

3 3 2 1 0
2 3 3 -1 1
1 -1 4 3 2
0 -1 -1 -1 1
1 2 2 1 0