// 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 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 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 jmatrix 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# 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[] matrixint[] output)  {  if (matrix[ij] != 'O' || output[ij] != -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[MN];  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[ij] + ' ');  }  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 

<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(ijdist)  {  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(ij) {  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(ijmatrixoutput) {  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>