CareerCup

Typed it in directly... so expect bugs (or plain incorrectness :P )
BFS initiated from all guard positions and +1 for reaching a naked position (a '0') and add it to queue to keep the BFS search going.

//Assuming N x N matrix and directions are up/down/left/right

#define IN_BOUNDARY(a,b) ((a)>=0 && (a)<N && (b)>=0 && (b)<N)

typedef struct { int x, y; } Pos;  //struct for a "position" of a node (indices)

//find and enqueue guard positions
queue <Pos> Q;
Pos temp;
int i, j;
for (i=0; i < N; i++)
	for(j=0; j < N; j++)
		if( A[i][j] == 'G' ) { 
			temp.x=i;
			temp.y=j;
			Q.push(temp); //putting guard position in Q
		}

//BFS 
while(!Q.empty()) {
	
	temp=Q.front(); Q.pop();
	i=temp.x;
	j=temp.y;  
	
	for( int u=-1; u < 2; u++)
		for( int v=-1; v < 2; v++)
			if( (!u||!v) && IN_BOUNDARY(i+u, j+v) && A[i+u][j+v]=='0')
			{
				//should reach here for only/all valid naked neighbours
				A[i+u][j+v]=A[i][j]+1;  //distance to neighbour is 1 more 
				
				temp.x=i+u;
				temp.y=j+v;
				Q.push(temp);  //push neighbour onto queue
			}
}

Below is my code, I did some test.
-2 for block, -1 for gurad.

void dfs(vector<vector<int>>& matrix, int x, int y, int step){
	if (x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size()) return;
	if (matrix[x][y] < 0) return;
	if (matrix[x][y]>step + 1 || matrix[x][y] == 0) 
		matrix[x][y] = step + 1;
	else return;
	dfs(matrix, x + 1, y, step + 1);
	dfs(matrix, x, y + 1, step + 1);
	dfs(matrix, x - 1, y, step + 1);
	dfs(matrix, x, y - 1, step + 1);
}

void RoomGuard(vector<vector<int>>&matrix){
	for (int i = 0; i < matrix.size(); i++){
		for (int j = 0; j < matrix[0].size(); j++){
			if (matrix[i][j] == -1){
				dfs(matrix, i-1, j, 0);
				dfs(matrix, i, j-1, 0);
				dfs(matrix, i +1, j, 0);
				dfs(matrix, i , j+1, 0);
			}
		}
	}
}

BFS from every guard. However: once you reach node whose distance from guard you do not improve, ignore it. If the matrix has N cells and G guards the complexity is O(NG);

import java.util.LinkedList;
import java.util.List;

import util.Utils;


public class MinDistanceFromGuards {


	private static int G = -1;
	private static int B = -2;


	public static void setDistances(int [][] mat){
		int nCols = mat[0].length;
		int nRows = mat.length;
		LinkedList<Node> guards = new LinkedList<>();
		for(int i = 0; i < nRows; i ++){
			for(int j = 0; j < nCols; j++){
				if(mat[i][j] == G) guards.add(new Node(i,j,0));
			}
		}


		LinkedList<Node> nodes = new LinkedList<>();
		while(!guards.isEmpty()){
			nodes.add(guards.removeFirst());
			while(!nodes.isEmpty()){
				Node cur = nodes.removeFirst(); // cur already processed
				int r = cur.row, c = cur.col;

				int matVal = mat[r][c];
				int dist = cur.dist;

				if(matVal >= 0) {
					if(matVal == 0 || dist < matVal) mat[r][c] = dist;
					else continue;
				}

				dist++;
				// above
				if(r > 0) addNode(nodes,mat,r-1, c, dist);
				// below
				if(r+1 < nRows) addNode(nodes,mat,r+1, c, dist);			
				//left 
				if(c > 0) addNode(nodes,mat,r,c-1, dist);
				//right 
				if(c+1 < nCols) addNode(nodes,mat,r,c+1, dist);

			}

		}




	}

	private static void addNode(List<Node> nodes, int [][]mat,  int r, int c, int val){
		if(mat[r][c] >=0) nodes.add(new Node(r,c,val));
	}


	private static class Node {
		int row;
		int col;
		int dist;

		Node(int r, int c, int val){
			row = r;
			col = c;
			dist = val;
		}
	}


	public static void main(String[] args) {
		int [][] mat = {
				{ 0, 0, 0 },
				{B, G, G},
				{B, 0, 0}
		};
		test(mat);

		int [][] mat2 = {
				{0, 0, B, 0, 0 },
				{B, G, 0, G, 0},
				{0, 0, B, B, 0},				
				{0, 0, 0, 0, 0}				
		};
		test(mat2);
		
		
		
		
	}

	private static void test(int[][] mat) {
		System.out.println("Input:");
		System.out.println(Utils.matrixToString(mat));
		setDistances(mat);
		
		System.out.println("Output:");
		System.out.println(Utils.matrixToString(mat));
		System.out.println("----------------------");
	}
	
}

bfs...

Could there be anything possibly wrong with using BFS and putting G nodes into the priority queue?

Here's another approach, Find the coordinate of the G nodes. For each node, find the Manhattan distance between the Coordinates and the G nodes, assign the value as the smallest manhattan distance. This takes O(n^3) though. The BFS technique with all G nodes in the Priority queue should be the fastest (as someone else suggested)

#include <iostream>                                                                                                     

int array[][3] = {{0,0,0},{-2,-1,-1},{-2,0,0}};

template <typename T>
T min(T a, T b)      
{                    
  if (a < b) return a;
  return b;           
}                     

void print()
{           
  for (int i = 0; i < 3; ++i)
  {                          
    for (int j = 0; j < 3; ++j)
    {                          
      std::cout << array[i][j] << ",";
    }                                 
    std::cout << "\n";                
  }                                   
}                                     

void markhere(int i, int j, int mark)
{
  if (array[i][j] > 0)
  {
    array[i][j] = min(array[i][j], mark);
  }
  else if (array[i][j] == 0)
  {
    array[i][j] = mark;
  }
}

void mark()
{
  bool done = false;
  int current =  -1;
  int mark = 1;
  while (!done)
  {
    done = true;
    for (int i = 0; i < 3; ++i)
    {
      for (int j  = 0 ; j < 3; ++j)
      {
        if (array[i][j] == current)
        {
          if (j > 0)
          {
            done = false;
            markhere(i, j - 1, mark);
          }
          if (j < 2)
          {
            done = false;
            markhere(i, j + 1, mark);
          }
          if (i < 2)
          {
            done = false;
            markhere(i + 1, j, mark);
          }
          if (i > 0)
          {
            done = false;
            markhere(i - 1, j, mark);
          }
        }
      }
    }
    current = mark;
    mark++;
  }
}

int main()
{
  print();
  mark();
  print();
  return 0;
}

time o(n) space o(n), get all the guard nodes to a min-heap and expand them to adjacent nodes, keep adding them to the min-heap if reachable. assuming obstacle is -2, guard is -1 for easy processing.

struct Node {
  int x;
  int y;
  int distance;
  
  Node(int x_i, int y_i, int distance_i) {
    x = x_i;
    y = y_i;
    distance = distance_i;
  }
  
  bool operator>(const Node &node) const {
    return distance > node.distance;
  }
};

void markDistance(vector<vector<int> >& map) {
  priority_queue<Node, vector<Node>, greater<Node> > min_heap;
  const int x_max = map.size() - 1;
  const int y_max = map[0].size() - 1;
  // get the guard nodes.
  for (int x = 0; x < map.size(); ++x) {
    for (int y = 0; y < map[x].size(); ++y) {
      if (map[x][y] == -1) {
        min_heap.emplace(x, y, 0);
      }
    }
  }
  while (!min_heap.empty()) {
    auto node = min_heap.top();
    min_heap.pop();
    for (int x = -1; x <= 1; ++x) {
      for (int y = -1; y <= 1; ++y) {
        // only visit the up/down/left/right node.
        if ((x == 0 && y == 0) || (x != 0 && y != 0)) continue;
        // get real (x, y) on the map
        int x_map = node.x + x;
        int y_map = node.y + y;
        // skip the node out of boundary or it's obstacle and guard
        if (x_map < 0 || y_map < 0 || x_map > x_max || y_map > y_max || 
            map[x_map][y_map] < 0) continue;
        // update the node if we have a shorter path to it or it's not visited.
        if (map[x_map][y_map] == 0 || node.distance + 1 < map[x_map][y_map]) {
          map[x_map][y_map] = node.distance + 1;
          min_heap.emplace(x_map, y_map, map[x_map][y_map]);
        }
      }
    }
  }
}

/* Readable C implementation, Compiled and tested. */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define Z 3

typedef struct pair {
	int p;
	int q;
} pair;

typedef struct queue {
	int front;
	int rear;
	pair *a;
	int n;
} queue;

queue *create_queue(int n)
{
	queue *q;
	q = malloc(sizeof(queue));
	q->a = calloc(sizeof(*(q->a)), n);
	if(!q) return q;
	q->n = n;
	q->front = -1;
	q->rear = -1;
	return q;
}

void enqueue(queue *q, pair p)
{
	if((q->front + 1) % q->n == q->rear) {
		printf("queue full\n");
		return;
	}

	q->front = (q->front + 1) % q->n;
	q->a[q->front] = p;

	if(q->rear == -1)
		q->rear = q->front;
}

int dequeue(queue *q, pair *p)
{
	if(q->front == -1)
		return -1;

	*p = q->a[q->rear];

	if(q->rear == q->front) {
		q->rear = -1;
		q->front = -1;
	} else {
		q->rear = (q->rear+1) % q->n;
	}
}

void visit(int m[Z][Z], int disc[Z][Z], int dist, int p, int q, queue *qu)
{
	pair p1;
	if(p < 0 || p >= Z || q < 0 || q >= Z)
		return;
	if(m[p][q] == 'G' || m[p][q] == 'B' || dist >= m[p][q])
		return;
	m[p][q] = dist;
	p1.p = p;
	p1.q = q;
	enqueue(qu, p1);
	disc[p][q] = 1;
}


void bfs(int m[Z][Z], int p, int q)
{
	queue *qu;
	pair p1;
	int disc[Z][Z] = {};
	int dist;

	if(m[p][q] != 'G')
		return;

	p1.p = p;
	p1.q = q;

	qu = create_queue(100);

	enqueue(qu, p1);
	disc[p1.p][p1.q] = 1;

	while(dequeue(qu, &p1) != -1) {
		if(m[p1.p][p1.q] == 'G')
			dist = 1;
		else
			dist = m[p1.p][p1.q] + 1;

		visit(m, disc, dist, p1.p-1, p1.q, qu);
		visit(m, disc, dist, p1.p+1, p1.q, qu);
		visit(m, disc, dist, p1.p, p1.q-1, qu);
		visit(m, disc, dist, p1.p, p1.q+1, qu);

	}
}

void find_dist(int m[Z][Z])
{
	int i, j;

	for(i = 0; i < Z; i++) {
		for(j = 0; j < Z; j++) {
			if(m[i][j] == 0)
				m[i][j] = INT_MAX;
		}
	}

	for(i = 0; i < Z; i++)
		for(j = 0; j < Z; j++)
			bfs(m, i, j);
}

int main()
{
	int i, j;
	int m[Z][Z] = {	{  0,   0,   0 },
			{ 'B', 'G', 'G'},
			{ 'B',  0,   0 }	};
	find_dist(m);

	for(i = 0; i < Z; i++) {
		for(j = 0; j < Z; j++) {
			if(m[i][j] >= 'A')
				printf("%c ", (char)m[i][j]);
			else
				printf("%d ", m[i][j]);

		}
		printf("\n");
	}

	return 0;
}

public void setMatrix(char[][] matrix) {
for (int i=0; i<matrix.length; i++) {
for(int j=0; j<matrix[0].length; j++) {
if (matrix[i][j] != 'B' && matrix[i][j] != 'G' && matrix[i][j] != '0') continue;
matrix[i][j] = findDistanceToGuardFrom(matrix, new Point(i, j));
}
}
}

private int findDistanceToGuardFrom(int[][] matrix, Point n) {
if (isGuard(n)) {
return 0;
}
int result;
for (Point ns : getNeighbors(matrix, n)) {
result = 1 + findDistanceToGuardFrom(matrix, ns);
if (matrix[n.x][n.y] == 0 || result < matrix[n.x][n.y]) { matrix[n.x][n.y] = result; }
}
return result;
}

Time Complexity O( n^2 log(n) ).....
I have check for various test cases it gives perfect answer.
input matrix will be like:

{int[][] query1 = new int[][]{ {0,0,0},
				 					  {1,2,2},
				 					  {1,0,0}};

where 2 means Guard and 1 mean blocked or obstacle
distance matrix is the output matrix, in which
Max value means cant reach,
0 means, you are a guard
otherwise other numeric values.

We keep checking whether the distance of any u, u_c has changed, if yes then we re-compute the distance matrix.

public int[][] getMinDistanceGuardMatrix(int[][] matrix){
		int[][] distance = new int[matrix.length][matrix[0].length];
		distance = initializeDistanceMatrix(distance);
		int maxCols = matrix[0].length;
		int maxRows = matrix.length;
		boolean alter = true;
		while(alter){
			alter = false;
			for (int u = 0; u < maxRows; u++){
				for(int u_c = 0; u_c < maxCols; u_c++){
					if(matrix[u][u_c] == 2 & distance[u][u_c]!=0) {
						distance[u][u_c] = 0;
//						System.out.println("2 " + u + "," + u_c + "= " + distance[u][u_c] );
						alter = true;
					} 
					else if(matrix[u][u_c] == 1) distance[u][u_c] = Integer.MAX_VALUE;
					else if(matrix[u][u_c]==0){
//						System.out.println("0 " + u + "," + u_c + "= " + distance[u][u_c] );
						int dist = Integer.MAX_VALUE;
						if(u_c + 1 < maxCols && (dist > distance[u][u_c+1])){
							dist = distance[u][u_c+1] + 1;
						}
						if(u_c - 1 > 0 && (dist > distance[u][u_c-1])){
							dist = distance[u][u_c-1] + 1;
						}
						if(u + 1 < maxRows && (dist > distance[u+1][u_c])){
							dist = distance[u+1][u_c] + 1;
							System.out.println("u+1 " + u + "," + u_c + "= " + dist );
						}
						if(u - 1 > 0 && (dist > distance[u-1][u_c])){
							dist = distance[u-1][u_c] + 1;
						}
//						System.out.println(" " + u + "," + u_c + "= " + dist );
//						System.out.println(" " + u + "," + u_c + "= " + distance[u][u_c] );
						if(distance[u][u_c] > dist){
							distance[u][u_c] = dist;
//							System.out.println("change " + u + "," + u_c + "= " + dist );
							alter = true;
						}
					}
				}
			}
//			printMatrix(distance);
		}
		
		return distance;

Find the all the guards first, populate all the surrounding empty rooms at distance 1, keep track of these rooms.
1.Find the G cells
2.Update the distance of surrounding cells found in step 1 to 1, use a list to keep track these cells been updated
3.Distance+1, repeat step 2, if the cell's distance is already there, that's definitely the shortest distance, skip this cell

public static int[][] nearestGuard(char[][] input) {
int[][] result = new int[input.length][input[0].length];
ArrayList<int[]> current = new ArrayList<int[]>();
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input[0].length; j++) {
if (input[i][j] == 'G')
current.add(new int[] { i, j });
}
}
int distance = 1;
while (!current.isEmpty()) {
ArrayList<int[]> next = new ArrayList<int[]>();
for (int[] c : current) {
guradHelper(input, c[0] + 1, c[1], distance, result, next);
guradHelper(input, c[0] - 1, c[1], distance, result, next);
guradHelper(input, c[0], c[1] + 1, distance, result, next);
guradHelper(input, c[0], c[1] - 1, distance, result, next);
}
current = next;
distance++;
}
return result;
}

public static void guradHelper(char[][] input, int i, int j, int distance,
int[][] result, ArrayList<int[]> next) {
if (i < 0 || j < 0 || i >= input.length || j >= input[0].length
|| input[i][j] == 'G' || input[i][j] == 'B'
|| result[i][j] != 0)
return;
result[i][j] = distance;
next.add(new int[] { i, j });
}

M = Given matrix
  Queue dequeue = put all the G coordinates in the queue.
  Queue queue = empty queue;
  while(!dequeue.isEmpty())
  {
    Pair p = dequeue.Dequeue();
    Enqueue all p's neighboring Rooms which are either '0' or less than 'p' value and increase its value by 1;
    if(dequeue.isEmpty())
    {
      temp = queue;
      queue = dequeue;
      dequeue = temp;
    }
  }

BFS from every guard. Not very efficient as I missed the idea of putting all of the guards in the queue and only doing one run using the zeros as visited indicators. But it works :)

void update_from_guard(char** a, int m, int n, int gx, int gy, bool first)
{
    bool** visited = new bool*[m];
    for (auto i = 0; i < m; ++i) visited[i] = new bool[n];
    for (auto i = 0; i < m; ++i)
        for (auto j = 0; j < n; ++j) visited[i][j] = false;
    std::queue<pt_t> q;
    q.push(pt_t(gx, gy, 0));
    visited[gx][gy] = true;
    while (!q.empty())
    {
        pt_t p = q.front();
        q.pop();
        int i = std::get<0>(p);
        int j = std::get<1>(p);
        int d = std::get<2>(p);
        if (a[i][j] >= '0' && a[i][j] <= '9')
        {
            if (first) a[i][j] = (char)('0' + d);
            else a[i][j] = std::min(a[i][j], (char)('0' + d));
        }
        else if (i != gx || j != gy) continue;
        if (i > 0 && !visited[i - 1][j])
        {
            q.push(pt_t(i - 1, j, d + 1));
            visited[i - 1][j] = true;
        }
        if (i < m - 1 && !visited[i + 1][j])
        {
            q.push(pt_t(i + 1, j, d + 1));
            visited[i + 1][j] = true;
        }
        if (j > 0 && !visited[i][j - 1])
        {
            q.push(pt_t(i, j - 1, d + 1));
            visited[i][j - 1] = true;
        }
        if (j < n-1 && !visited[i][j + 1])
        {
            q.push(pt_t(i, j + 1, d + 1));
            visited[i][j + 1] = true;
        }
    }
    for (auto i = 0; i < m; ++i) delete[] visited[i];
    delete[] visited;
}

void calc_min_guard_dist(char** a, int m, int n)
{
    bool seen_guard = false;
    for (auto i = 0; i < m; ++i)
        for (auto j = 0; j < n; ++j)
            if (a[i][j] == 'G') 
            { 
                update_from_guard(a, m, n, i, j, !seen_guard);
                seen_guard = true;
            }
}

void print_matrix(char** a, int m, int n)
{
    for (auto i = 0; i < m; ++i)
    { 
        for (auto j = 0; j < n; ++j)
            std::cout << a[i][j] << " ";
        std::cout << std::endl;
    }
}

void test_calc_min_guard_dist()
{
    const int m = 3, n = 3;
    char** a = new char*[m];
    for (auto i = 0; i < m; ++i) a[i] = new char[n];
    for (auto i = 0; i < m; ++i)
        for (auto j = 0; j < n; ++j)
            a[i][j] = '0';
    a[1][0] = 'B';
    a[2][0] = 'B';
    a[1][1] = 'G';
    a[1][2] = 'G';
    print_matrix(a, m, n);
    calc_min_guard_dist(a, m, n);
    print_matrix(a, m, n);
}

Initially i walk through all the nodes and store the coordinates of guards and rooms. I then calculate the absolute difference of the coordinates from room to guards to get the result.

Here is a working python code:

in_matrix = [[0,0,0],['B','G','G'],['B',0,0]]
room_pointers  = []
guard_pointers = []

out_matrix = in_matrix

"define a class to store the coordinates of rooms and guards"
class coordinates:
    def __init__(self,x,y):
        self.x = x
        self.y = y

def calculate_steps():
    for i in range(len(in_matrix)):
        for j in range(len(in_matrix[0])):
            if(in_matrix[i][j]==0):
                room_pointers.append(coordinates(i,j))
            elif(in_matrix[i][j]=='G'):
                guard_pointers.append(coordinates(i,j))

    for i in range(len(in_matrix)):
        for j in range(len(in_matrix[0])):
            if(in_matrix[i][j] == 0):
                room = room_pointers[0]
                sum = 5
                for guard in guard_pointers:
                    temp = abs(guard.x-room.x)+abs(guard.y-room.y)
                    if(temp < sum): sum = temp
                out_matrix[i][j] = sum
                del room_pointers[0] 

    print("The steps from a room to nearest Guard room is: ")
    print(out_matrix)

calculate_steps()

I did this question in python and basically did BFS twice. once to find where the G's are and then to spread out from the G's using a dictionary to keep track of the minimum distances dynamically.

def roomDist(matrix):
	distDict = {}
	coord = (0,0)
	q = [coord]
	visited = []
	visitedG = []
	while (q != []):
		coord = q.pop(0)
		i = coord[0]
		j = coord[1]
		element = matrix[i][j]
		if (element == "G"):
			visitedG.append(coord)
			distDict[coord] = 1
		elif (element == "B"):
			distDict[coord] = float("inf")
		visited.append(coord)
		neighbors = getNeighbors(matrix,i,j,visited) # returns only the NON VISITED and NON OBSTACLE neighbors
		for n in neighbors:
			if (n not in q):
				q.append(n)
	newDict = roomDistHelper(matrix,visitedG,distDict)
	print("\n")
	for row in matrix:
		t = ""
		for element in row:
			t += element + "\t"
		print(t)

	for e in newDict.keys():
		i = e[0]
		j = e[1]
		element = matrix[i][j]
		if (element == "0"):
			matrix[i][j] = newDict[e]
	print("Updated matrix:\n")
	for row in matrix:
		t = ""
		for element in row:
			t += str(element) + "\t"
		print(t)

def roomDistHelper(matrix,visitedG,distDict):
	q = visitedG
	visited = []
	while (q != []):
		coord = q.pop(0)
		i = coord[0]
		j = coord[1]
		element = matrix[i][j]
		visited.append(coord)
		neighbors = getNeighbors(matrix,i,j,visited)
		for nei in neighbors:
			if (nei not in q):
				q.append(nei)
		curValue = distDict.get(coord)
		allN = allNeighbors(matrix,i,j)
		for n in allN:
			if (element == "G"):
				distDict[n] = 1
			else:
				val = distDict.get(n,float("inf"))
				distDict[n] = min(1 + curValue,val)
	return distDict
		
def allNeighbors(matrix,i,j):
	rList = []
	right = (i+1,j) if i+1 < len(matrix) else None
	down = (i,j+1) if j+1 < len(matrix[0]) else None
	left = (i-1,j) if i-1 >= 0 else None
	up = (i,j-1) if j-1 >= 0 else None
	if(right is not None and matrix[right[0]][right[1]] != "B"):
		rList.append(right)
	if(left is not None and matrix[left[0]][left[1]] != "B"):
		rList.append(left)
	if(up is not None and matrix[up[0]][up[1]] != "B"):
		rList.append(up)
	if(down is not None and matrix[down[0]][down[1]] != "B"):
		rList.append(down)
	return rList


def getNeighbors(matrix,i,j,visited):
	rList = []
	right = (i+1,j) if i+1 < len(matrix) else None
	down = (i,j+1) if j+1 < len(matrix[0]) else None
	left = (i-1,j) if i-1 >= 0 else None
	up = (i,j-1) if j-1 >= 0 else None
	if(right is not None and matrix[right[0]][right[1]] != "B" and right not in visited):
		rList.append(right)
	if(left is not None and matrix[left[0]][left[1]] != "B"and left not in visited):
		rList.append(left)
	if(up is not None and matrix[up[0]][up[1]] != "B" and up not in visited):
		rList.append(up)
	if(down is not None and matrix[down[0]][down[1]] != "B" and down not in visited):
		rList.append(down)
	return rList

static class Coordinate {
    int x, y;

    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public static void distance(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return;
    }

    Queue<Coordinate> q = new LinkedList<>();

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 'G') {
                q.add(new Coordinate(i, j));
            }
        }
    }

    final int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

    while (!q.isEmpty()) {
        Coordinate curr = q.remove();

        for (int[] dir : dirs) {
            int x = curr.x + dir[0];
            int y = curr.y + dir[1];

            if (isValid(matrix, x, y) && matrix[x][y] == '0') {
                matrix[x][y] = matrix[curr.x][curr.y] == 'G'
                        ? '1'
                        : (char) (matrix[curr.x][curr.y] + 1);
                q.add(new Coordinate(x, y));
            }
        }
    }

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == '0') {
                matrix[i][j] = 'X';
            }
        }
    }
}

private static boolean isValid(char[][] matrix, int x, int y) {
    return x >= 0 && x < matrix.length
            && y >= 0 && y < matrix[0].length;
}

Dijkstra's algorithm should be better. And it has O(n^2) complexity.

What about find shortest path from all guards? Just put them into one queue initially.

public static int guards(String [][]a, int i, int j, int N, int [][]visited){
		int c;
		
		// Returns if you encounter a "B" or Index is out of bound
		if (i < 0 || j < 0 || i >= N || j >= N || a[i][j] == "B")
			return 0;

		// If the code encounters a numeric value (minimum value) it returns (numeric value + 1). The numeric value is minimum value to reach "G"
		// Using this principle you need not check the shortest distance to G for every index in the Array. 
		// You can simply return if you encounter B, G, Numeric value.
		
		// Consider 	2 1 B
		//			1 G B
		//			0 1 G
		// Array[2][0] need not check for G, its neighbor Array[1][0] or Array[2][1] (depending on the recursive call) has the minimum value of 1.
		// Thus Array[2][0] minimum value is 1 + min step for Array[1][0] = 2.
		// This may or may not be Array[2][0] minimum value depending on the number of recursive calls left.
		
		if (isNumeric(a[i][j]) && Integer.parseInt(a[i][j]) > 0)
			return 1+Integer.parseInt(a[i][j]);

		if (a[i][j] == "G")
			return 1;
		
		if (visited[i][j]==0){
		
			visited[i][j]=1;
	
			// Consider the minimum value
			if ((c=guards(a,i-1,j,N,visited))>0)
				a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";
	
			if ((c = guards(a,i,j+1,N,visited))>0)
				a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";
	
			if ((c = guards(a,i+1,j,N,visited))>0)
				a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";
	
			if ((c = guards(a,i,j-1,N,visited))>0)
				a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";
			
			visited[i][j]=0;
			
			// Consider that an index's neighbor has found a G. 
			// Since the numeric value determined be the neighbor is the minimum, minimum value for index will be 1 + neighbor's numeric value. 
			return 1+Integer.parseInt(a[i][j]);
			
		}
		
		return 0;

	}

	public static boolean isNumeric(String s){

		for(char c: s.toCharArray()){
			if(!Character.isDigit(c))
				return false;
		}
		return true;
	}

	public static void guard(String a[][]){
		int N=a.length;
		int visited[][]=new int[N][N];
		
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				visited[i][j]=0;
		
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				if(a[i][j] != "B" && a[i][j] != "G" && Integer.parseInt(a[i][j])==0)
					guards(a,i,j,N,visited);

}

I have hard coded the dimension as 3.
-1 will represent block, -2 will represent guard.

public class FindNearestGuard {

	int[] xDiff = {0,-1, 0, 1};
	int[] yDiff = {1, 0,-1, 0};
	
	
	int[][] matrix = {{0,0,0},
			          {-1,-2,-2},
			          {-1,0,0}};

	boolean[][] visited = new boolean[3][3];	
	public void findDistance()
	{
		int n =3;
		int[][] dup = new int[3][3];
		for(int i = 0 ; i < 3 ;i++)
		{
			for(int j = 0 ; j < 3 ; j++)
			{
				dup[i][j] = matrix[i][j];
			}
		}
		
		for(int i = 0 ; i < 3 ; i++)
		{
			for(int j = 0 ; j < 3 ; j++)
			{
				if (matrix[i][j] == 0)
				{
					int res = find(i,j, 0);
					dup[i][j] = res;
				}
			}
		}
		
		for(int i = 0 ; i < 3 ; i++)
		{
			for(int j = 0 ; j < 3 ; j++)
			{
				System.out.print(dup[i][j]);
			}
			System.out.println();
		}
	}
	
	private int find(int x, int y, int count)
	{
	    if (matrix[x][y] == -2)
	    {
	    	return count;
	    }
	    int min = Integer.MAX_VALUE;
	    
	    for(int i = 0 ; i< 4 ; i++)
	    {
	    	int x1 = x + xDiff[i];
	    	int y1 = y + yDiff[i];
	    	if (isValid(x1, y1)&& !visited[x1][y1]&& matrix[x1][y1] != -1)
	    	{
	    		visited[x][y] = true;
	    		int c = find(x1, y1, count+1);
	    		visited[x][y] = false;
	    		if (c < min)
	    		{
	    			min = c;
	    		}
	    	}
	    }
	    
	    return min;
	}
	
	private boolean isValid(int x, int y)
	{
		return x >= 0 && x < 3 && y >= 0 && y < 3;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
        new FindNearestGuard().findDistance();

	}

}