Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
^^^ Yes, because all growing shortest paths start at a G and go through a '0' (they do not revisit a numbered node again).
My "Lol" comment above was referring to this fix:
A[i+u][j+v]=A[i][j]+1;
should be
A[i+u][j+v]= (A[i][j]=='G')? 1: A[i][j]+1;
Can this algorith ensure that the distance is from the nearest Guard point, I think we have to write like this :
if(A[i + u][j + v] == 0 || A[i+u][j+v] > A[i][j] +1)
A[i+u][j+v] = A[i][j] + 1
I think the algorithm didn't handle the nearest gaurd points case. Your algorithm might return the longest routes to all the 0 from a given set of gaurds. What if the gaurd point you are starting is not the right candidate for a '0' zero node. There is a possibility that this '0' node can be reached from another gaurd point which is much close.
So we need to correct the logic to take the min( existing a[i][j] and new a[i][j])
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);
}
}
}
}
I am not sure :(
How can you guarantee that "step" is always the shortest path reachable from that guard? Can you explain it?
Paint fill is boolean filling of nodes...so dfs vs.bfs has same effect because u are just visiting all suitable nodes.
This is shortest distance filling... So dfs usually does not work.
@Mem, took a closer look, and I see what you are doing here. You are repeatedly trying all paths, even if they reuse the same spots, so long as going through the spot is cheaper than any previous path through that spot.
Cool idea!
The idea should work but it worst case complexity should be large.
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("----------------------");
}
}
Yes, bfs. But interviewer said there is an optimal solution with O(n^2), which I haven't figured out. :(
I think we can use bfs twice to solve this problem, from node (0,0) to (n,n), then reverse from (n,n) to (0,0)
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;
}
Could you please elaborate a bit more. Interviewer does mention to start from G, and then bfs from there. but I've run out of time by then. Thanks
This is what I thought, start from every G, go 4 direction, if we find current cell is B or another G we return, or if it is a number that smaller than the step we have from Current G, we also return other wise add 1 to current step and put it into current cell. Do the same recursion for current cell until no move can made. Do the same process for all G.
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);
}
Could the person who wrote the answer, care to explain what the frack he is trying to do, first?
Mr. frack,
The code uses dynamic programming to find the minimum distance to the nearest guards. For example:
Consider 3 points A, B, C
Distance: B to C = 3 (shortest distance)
Distance: A to B = 2 (shortest distance)
Distance: A to C = ?
Option 1: find shortest distance from A to C by traveling from A to C
Option 2: Add shortest distance from A to B and shortest distance from B to C.
Above code uses Option 2.
Next time you down vote an answer, have a better reason than being lazy. Also please provide a test case that fails.
if you are at point A and you want to goto point C, and you re
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();
}
}
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.
- S O U N D W A V E March 10, 2014