पायथन में बैंक में गार्ड से सबसे छोटी दूरी खोजें

मान लीजिए हमारे पास एक मैट्रिक्स है जो तीन अक्षरों 'O', 'G', और 'W' से भरा है जहां 'O' खुली जगह दर्शाता है, 'G' गार्ड्स दर्शाता है और 'W' बैंक में दीवारें दर्शाता है, हमें मैट्रिक्स में सभी O's को एक गार्ड से उनकी सबसे छोटी दूरी के संबंध में बदलना है, हम किसी भी दीवार से नहीं जा सकते। आउटपुट मैट्रिक्स में गार्ड्स को 0 से और दीवारों को -1 से बदला जाता है।

तो, यदि इनपुट इस तरह है:

तो आउटपुट होगा:

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

• M := 5

• N := 5

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

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

• is_ok() फंक्शन परिभाषित करें। यह i, j लेगा।

• यदि (i, 0 और M की रेंज में) या (j, 0 और j N की रेंज में), तो:

  • False लौटाएं

• True लौटाएं

• isSafe() फंक्शन परिभाषित करें। यह i, j, matrix, result लेगा।

• यदि matrix[i, j] 'O' नहीं है या result[i, j] -1 नहीं है, तो:

  • False लौटाएं

• True लौटाएं

• calculate_dist() फंक्शन परिभाषित करें। यह matrix लेगा।

• result := M x N क्रम का एक मैट्रिक्स बनाएं और -1 से भरें

• एक डबल एंडेड क्यू q परिभाषित करें

• i को 0 से M तक के लिए, करें:

  • j को 0 से N तक के लिए, करें:

    • result[i, j] := -1

    • यदि matrix[i, j], 'G' के समान है, तो:

      • pos := [i, j, 0]

      • pos को q के बाएं में डालें

      • result[i, j] := 0

• जब q का आकार > 0 शून्येतर है, करें:

  • curr := q से अंतिम तत्व हटाएं

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

  • i को 0 से 3 तक के लिए, करें:

    • यदि is_ok(x+dir_row[i], y+dir_col[i]) शून्येतर है और 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]

      • pos को q के बाएं में डालें

• i को 0 से M तक के लिए, करें:

  • j को 0 से N तक के लिए, करें:

    • result[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