给定一个用“O”、“G”和“W”填充的矩阵，其中“O”代表开放空间，“G”代表警卫，“W”代表银行的墙壁。将矩阵中的所有O替换为与防护装置之间的最短距离，但不能穿过任何墙壁。此外，在输出矩阵中，将防护装置替换为0，将墙替换为-1。 预期 时间复杂性 是M×N矩阵的O（MN）。
null
例如：
O ==> Open SpaceG ==> GuardW ==> WallInput: O O O O G O W W O O O O O W O G W W W O O O O O GOutput: 3 3 2 1 0 2 -1 -1 2 1 1 2 3 -1 2 0 -1 -1 -1 1 1 2 2 1 0
这个想法是做BFS。我们首先让所有包含守卫和循环的单元排队，直到队列不为空。对于循环的每次迭代，我们将前面的单元从队列中出列，对于其四个相邻单元中的每一个，如果单元是开放区域，且其与防护装置的距离尚未计算，我们将更新其距离并将其入列。最后在BFS程序结束后，我们打印距离矩阵。
以下是上述理念的实施——
C++
// C++ program to replace all of the O's in the matrix // with their shortest distance from a guard #include <bits/stdc++.h> using namespace std; // store dimensions of the matrix #define M 5 #define N 5 // An Data Structure for queue used in BFS struct queueNode { // i, j and distance stores x and y-coordinates // of a matrix cell and its distance from guard // respectively int i, j, distance; }; // These arrays are used to get row and column // numbers of 4 neighbors of a given cell int row[] = { -1, 0, 1, 0}; int col[] = { 0, 1, 0, -1 }; // return true if row number and column number // is in range bool isValid( int i, int j) { if ((i < 0 || i > M - 1) || (j < 0 || j > N - 1)) return false ; return true ; } // return true if current cell is an open area and its // distance from guard is not calculated yet bool isSafe( int i, int j, char matrix[][N], int output[][N]) { if (matrix[i][j] != 'O' || output[i][j] != -1) return false ; return true ; } // Function to replace all of the O's in the matrix // with their shortest distance from a guard void findDistance( char matrix[][N]) { int output[M][N]; queue<queueNode> q; // finding Guards location and adding into queue for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) { // initialize each cell as -1 output[i][j] = -1; if (matrix[i][j] == 'G' ) { queueNode pos = {i, j, 0}; q.push(pos); // guard has 0 distance output[i][j] = 0; } } } // do till queue is empty while (!q.empty()) { // get the front cell in the queue and update // its adjacent cells queueNode curr = q.front(); int x = curr.i, y = curr.j, dist = curr.distance; // do for each adjacent cell for ( int i = 0; i < 4; i++) { // if adjacent cell is valid, has path and // not visited yet, en-queue it. if (isSafe(x + row[i], y + col[i], matrix, output) && isValid(x + row[i], y + col[i])) { output[x + row[i]][y + col[i]] = dist + 1; queueNode pos = {x + row[i], y + col[i], dist + 1}; q.push(pos); } } // dequeue the front cell as its distance is found q.pop(); } // print output matrix for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) cout << std::setw(3) << output[i][j]; cout << endl; } } // Driver code int main() { char matrix[][N] = { { 'O' , 'O' , 'O' , 'O' , 'G' }, { 'O' , 'W' , 'W' , 'O' , 'O' }, { 'O' , 'O' , 'O' , 'W' , 'O' }, { 'G' , 'W' , 'W' , 'W' , 'O' }, { 'O' , 'O' , 'O' , 'O' , 'G' } }; findDistance(matrix); return 0; } |
JAVA
// Java program to replace all of the O's // in the matrix with their shortest // distance from a guard package Graphs; import java.util.LinkedList; import java.util.Queue; public class MinDistanceFromaGuardInBank{ // Store dimensions of the matrix int M = 5 ; int N = 5 ; class Node { int i, j, dist; Node( int i, int j, int dist) { this .i = i; this .j = j; this .dist = dist; } } // These arrays are used to get row // and column numbers of 4 neighbors // of a given cell int row[] = { - 1 , 0 , 1 , 0 }; int col[] = { 0 , 1 , 0 , - 1 }; // Return true if row number and // column number is in range boolean isValid( int i, int j) { if ((i < 0 || i > M - 1 ) || (j < 0 || j > N - 1 )) return false ; return true ; } // Return true if current cell is // an open area and its distance // from guard is not calculated yet boolean isSafe( int i, int j, char matrix[][], int output[][]) { if (matrix[i][j] != 'O' || output[i][j] != - 1 ) return false ; return true ; } // Function to replace all of the O's // in the matrix with their shortest // distance from a guard void findDistance( char matrix[][]) { int output[][] = new int [M][N]; Queue<Node> q = new LinkedList<Node>(); // Finding Guards location and // adding into queue for ( int i = 0 ; i < M; i++) { for ( int j = 0 ; j < N; j++) { // Initialize each cell as -1 output[i][j] = - 1 ; if (matrix[i][j] == 'G' ) { q.add( new Node(i, j, 0 )); // Guard has 0 distance output[i][j] = 0 ; } } } // Do till queue is empty while (!q.isEmpty()) { // Get the front cell in the queue // and update its adjacent cells Node curr = q.peek(); int x = curr.i; int y = curr.j; int dist = curr.dist; // Do for each adjacent cell for ( int i = 0 ; i < 4 ; i++) { // If adjacent cell is valid, has // path and not visited yet, // en-queue it. if (isValid(x + row[i], y + col[i])) { if (isSafe(x + row[i], y + col[i], matrix, output)) { output[x + row[i]][y + col[i]] = dist + 1 ; q.add( new Node(x + row[i], y + col[i], dist + 1 )); } } } // Dequeue the front cell as // its distance is found q.poll(); } // Print output matrix for ( int i = 0 ; i < M; i++) { for ( int j = 0 ; j < N; j++) { System.out.print(output[i][j] + " " ); } System.out.println(); } } // Driver code public static void main(String args[]) { char matrix[][] = { { 'O' , 'O' , 'O' , 'O' , 'G' }, { 'O' , 'W' , 'W' , 'O' , 'O' }, { 'O' , 'O' , 'O' , 'W' , 'O' }, { 'G' , 'W' , 'W' , 'W' , 'O' }, { 'O' , 'O' , 'O' , 'O' , 'G' } }; MinDistanceFromaGuardInBank g = new MinDistanceFromaGuardInBank(); g.findDistance(matrix); } } // This code is contributed by Shobhit Yadav |
Python3
# Python3 program to replace all of the O's in the matrix # with their shortest distance from a guard from collections import deque as queue # store dimensions of the matrix M = 5 N = 5 # These arrays are used to get row and column # numbers of 4 neighbors of a given cell row = [ - 1 , 0 , 1 , 0 ] col = [ 0 , 1 , 0 , - 1 ] # return true if row number and column number # is in range def isValid(i, j): if ((i < 0 or i > M - 1 ) or (j < 0 or j > N - 1 )): return False return True # return true if current cell is an open area and its # distance from guard is not calculated yet def isSafe(i, j,matrix, output): if (matrix[i][j] ! = 'O' or output[i][j] ! = - 1 ): return False return True # Function to replace all of the O's in the matrix # with their shortest distance from a guard def findDistance(matrix): output = [[ - 1 for i in range (N)] for i in range (M)] q = queue() # finding Guards location and adding into queue for i in range (M): for j in range (N): # initialize each cell as -1 output[i][j] = - 1 if (matrix[i][j] = = 'G' ): pos = [i, j, 0 ] q.appendleft(pos) # guard has 0 distance output[i][j] = 0 # do till queue is empty while ( len (q) > 0 ): # get the front cell in the queue and update # its adjacent cells curr = q.pop() x, y, dist = curr[ 0 ], curr[ 1 ], curr[ 2 ] # do for each adjacent cell for i in range ( 4 ): # if adjacent cell is valid, has path and # not visited yet, en-queue it. if isValid(x + row[i], y + col[i]) and isSafe(x + row[i], y + col[i], matrix, output) : output[x + row[i]][y + col[i]] = dist + 1 pos = [x + row[i], y + col[i], dist + 1 ] q.appendleft(pos) # print output matrix for i in range (M): for j in range (N): if output[i][j] > 0 : print (output[i][j], end = " " ) else : print (output[i][j],end = " " ) print () # Driver code matrix = [[ 'O' , 'O' , 'O' , 'O' , 'G' ], [ 'O' , 'W' , 'W' , 'O' , 'O' ], [ 'O' , 'O' , 'O' , 'W' , 'O' ], [ 'G' , 'W' , 'W' , 'W' , 'O' ], [ 'O' , 'O' , 'O' , 'O' , 'G' ]] findDistance(matrix) # This code is contributed by mohit kumar 29 |
C#
// C# program to replace all of the O's // in the matrix with their shortest // distance from a guard using System; using System.Collections.Generic; public class Node { public int i, j, dist; public Node( int i, int j, int dist) { this .i = i; this .j = j; this .dist = dist; } } public class MinDistanceFromaGuardInBank { // Store dimensions of the matrix static int M = 5; static int N = 5; // These arrays are used to get row // and column numbers of 4 neighbors // of a given cell static int [] row = { -1, 0, 1, 0 }; static int [] col = { 0, 1, 0, -1 }; // Return true if row number and // column number is in range static bool isValid( int i, int j) { if ((i < 0 || i > M - 1) || (j < 0 || j > N - 1)) return false ; return true ; } // Return true if current cell is // an open area and its distance // from guard is not calculated yet static bool isSafe( int i, int j, char [,] matrix, int [,] output) { if (matrix[i,j] != 'O' || output[i,j] != -1) { return false ; } return true ; } // Function to replace all of the O's // in the matrix with their shortest // distance from a guard static void findDistance( char [,] matrix) { int [,] output = new int [M,N]; Queue<Node> q = new Queue<Node>(); // Finding Guards location and // adding into queue for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) { // Initialize each cell as -1 output[i, j] = -1; if (matrix[i, j] == 'G' ) { q.Enqueue( new Node(i, j, 0)); // Guard has 0 distance output[i, j] = 0; } } } // Do till queue is empty while (q.Count != 0) { // Get the front cell in the queue // and update its adjacent cells Node curr = q.Peek(); int x = curr.i; int y = curr.j; int dist = curr.dist; // Do for each adjacent cell for ( int i = 0; i < 4; i++) { // If adjacent cell is valid, has // path and not visited yet, // en-queue it. if (isValid(x + row[i], y + col[i])) { if (isSafe(x + row[i], y + col[i],matrix, output)) { output[x + row[i] , y + col[i]] = dist + 1; q.Enqueue( new Node(x + row[i],y + col[i],dist + 1)); } } } // Dequeue the front cell as // its distance is found q.Dequeue(); } // Print output matrix for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) { Console.Write(output[i,j] + " " ); } Console.WriteLine(); } } // Driver code static public void Main () { char [,] matrix ={ { 'O' , 'O' , 'O' , 'O' , 'G' }, { 'O' , 'W' , 'W' , 'O' , 'O' }, { 'O' , 'O' , 'O' , 'W' , 'O' }, { 'G' , 'W' , 'W' , 'W' , 'O' }, { 'O' , 'O' , 'O' , 'O' , 'G' } }; findDistance(matrix); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program to replace all of the O's // in the matrix with their shortest // distance from a guard // Store dimensions of the matrix let M = 5; let N = 5; class Node { constructor(i,j,dist) { this .i = i; this .j = j; this .dist = dist; } } // These arrays are used to get row // and column numbers of 4 neighbors // of a given cell let row=[-1, 0, 1, 0]; let col=[0, 1, 0, -1 ]; // Return true if row number and // column number is in range function isValid(i,j) { if ((i < 0 || i > M - 1) || (j < 0 || j > N - 1)) return false ; return true ; } // Return true if current cell is // an open area and its distance // from guard is not calculated yet function isSafe(i,j,matrix,output) { if (matrix[i][j] != 'O ' || output[i][j] != -1) return false; return true; } // Function to replace all of the O' s // in the matrix with their shortest // distance from a guard function findDistance(matrix) { let output = new Array(M); for (let i=0;i<M;i++) { output[i]= new Array(N); } let q = []; // Finding Guards location and // adding into queue for (let i = 0; i < M; i++) { for (let j = 0; j < N; j++) { // Initialize each cell as -1 output[i][j] = -1; if (matrix[i][j] == 'G' ) { q.push( new Node(i, j, 0)); // Guard has 0 distance output[i][j] = 0; } } } // Do till queue is empty while (q.length!=0) { // Get the front cell in the queue // and update its adjacent cells let curr = q[0]; let x = curr.i; let y = curr.j; let dist = curr.dist; // Do for each adjacent cell for (let i = 0; i < 4; i++) { // If adjacent cell is valid, has // path and not visited yet, // en-queue it. if (isValid(x + row[i], y + col[i])) { if (isSafe(x + row[i], y + col[i], matrix, output)) { output[x + row[i]][y + col[i]] = dist + 1; q.push( new Node(x + row[i], y + col[i], dist + 1)); } } } // Dequeue the front cell as // its distance is found q.shift(); } // Print output matrix for (let i = 0; i < M; i++) { for (let j = 0; j < N; j++) { document.write(output[i][j] + " " ); } document.write( "<br>" ); } } // Driver code let matrix=[[ 'O' , 'O' , 'O' , 'O' , 'G' ], [ 'O' , 'W' , 'W' , 'O' , 'O' ], [ 'O' , 'O' , 'O' , 'W' , 'O' ], [ 'G' , 'W' , 'W' , 'W' , 'O' ], [ 'O' , 'O' , 'O' , 'O' , 'G' ]]; findDistance(matrix); // This code is contributed by ab2127 </script> |
输出：
3 3 2 1 0 2 -1 -1 2 1 1 2 3 -1 2 0 -1 -1 -1 1 1 2 2 1 0
本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
