Намерете най-краткото разстояние от пазач в банка
Дадена е матрица, която е изпълнена с „O“, „G“ и „W“, където „O“ представлява отворено пространство, „G“ представлява пазачи, а „W“ представлява стени в банка. Заменете всички O в матрицата с най-късото им разстояние от пазач, без да можете да преминете през стени. Също така заменете предпазителите с 0 и стените с -1 в изходната матрица.
Очаквано Времева сложност е O(MN) за матрица M x N.
Очаквано Помощно пространство е O(MN) за матрица M x N.
Примери:
O ==> Open Space G ==> Guard W ==> Wall Input: 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 Output: 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 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 ( '
' ); } } // 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
Времева сложност: O(n*m)
Помощно пространство: O(n*m)
