Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
import java.util.Arrays;
public class MuseumGuardian {
static int[] moveX = {0, 0, 1, -1};
static int[] moveY = {1, -1, 0, 0};
public static void main(String[] args) {
char[][] board =
{
{'.', '#', '.', 'G', 'G'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}
};
solve(board);
for (char[] arr : board) {
System.out.println(Arrays.toString(arr));
}
}
/// Helper Methods
static int atoi(char c) {
return c - '0';
}
static char itoa(int n) {
return (char)('0' + n);
}
public static void solve(char[][] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 'G') {
markNeighbors(A, i, j, 0);
}
}
}
}
public static boolean isSafe(char[][] A, int i, int j, int newValue) {
if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
return false;
}
if (A[i][j] == 'G' || A[i][j] == '#') {
return false;
}
if (A[i][j] != '.' && atoi(A[i][j]) <= newValue) {
return false;
}
return true;
}
public static void markNeighbors(char[][] A, int i, int j, int value) {
for (int k = 0; k < moveX.length; k++) {
int nextX = i + moveX[k];
int nextY = j + moveY[k];
if (isSafe(A, nextX, nextY, value + 1)) {
A[nextX][nextY] = itoa(value + 1);
markNeighbors(A, nextX, nextY, value + 1);
}
}
}
}
import java.util.Arrays;
public class MuseumGuardian {
static int[] moveX = {0, 0, 1, -1};
static int[] moveY = {1, -1, 0, 0};
public static void main(String[] args) {
char[][] board =
{
{'.', '#', '.', 'G', 'G'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}
};
solve(board);
for (char[] arr : board) {
System.out.println(Arrays.toString(arr));
}
}
/// Helper Methods
static int atoi(char c) {
return c - '0';
}
static char itoa(int n) {
return (char)('0' + n);
}
public static void solve(char[][] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 'G') {
markNeighbors(A, i, j, 0);
}
}
}
}
public static boolean isSafe(char[][] A, int i, int j, int newValue) {
if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
return false;
}
if (A[i][j] == 'G' || A[i][j] == '#') {
return false;
}
if (A[i][j] != '.' && atoi(A[i][j]) <= newValue) {
return false;
}
return true;
}
public static void markNeighbors(char[][] A, int i, int j, int value) {
for (int k = 0; k < moveX.length; k++) {
int nextX = i + moveX[k];
int nextY = j + moveY[k];
if (isSafe(A, nextX, nextY, value + 1)) {
A[nextX][nextY] = itoa(value + 1);
markNeighbors(A, nextX, nextY, value + 1);
}
}
}
}
I don't feel like writing the code for this, but the process is basically to BFS from the guards, and for each empty space, record the depth from the guard in the BFS -> depth of parent + 1. Since we will do multiple BFS's record the minimum depth if it this is possible.
@SK I believe that approach should work, so there would be N BFSs for N Guard Cells, each cell would output a Matrix char[][], merge the matrix into one single matrix picking the Min depth of each cell m[i][j], return the resulting merged matrix.
public static void main(String[] args){
String[][] input = new String[4][5];
input[0][0] = ".";
input[0][1] = "#";
input[0][2] = ".";
input[0][3] = "G";
input[0][4] = ".";
input[1][0] = ".";
input[1][1] = ".";
input[1][2] = "#";
input[1][3] = ".";
input[1][4] = ".";
input[2][0] = "G";
input[2][1] = ".";
input[2][2] = ".";
input[2][3] = ".";
input[2][4] = ".";
input[3][0] = ".";
input[3][1] = ".";
input[3][2] = "#";
input[3][3] = ".";
input[3][4] = ".";
printInput(input);
getDistanceMatrix(input);
printInput(input);
}
static void printInput(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
System.out.print(input[row][col]);
if(col == input[0].length-1){
System.out.print("\n");
}
}
}
}
static void getDistanceMatrix(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
if(input[row][col].equals(".")){
input[row][col] = getDistance(input, row, col);
}
}
}
}
static String getDistance(String[][] input, int row, int col){
int MAX = Integer.MAX_VALUE;
int rowDistance = MAX;
int r = row;
//previous row
while(r > 0){
r--;
if(input[r][col].equals("G")){
rowDistance = 1;
break;
}
try{
rowDistance = Integer.parseInt(input[r][col])+1;
break;
}catch(Exception e){
}
}
int guardIdx = -1;
int obstacleNum = 0;
// next row
for(r = row+1; r < input.length; r++){
if(input[r][col].equals("G")){
guardIdx = r;
break;
}
if(input[r][col].equals("#")){
obstacleNum++;
}
}
if(guardIdx > 0){
rowDistance = Math.min(rowDistance, guardIdx-row-obstacleNum);
}
int colDistance = MAX;
int c = col;
//previous col
while(c > 0){
c--;
if(input[row][c].equals("G")){
rowDistance = 1;
break;
}
try{
colDistance = Integer.parseInt(input[row][c])+1;
break;
}catch(Exception e){
}
}
guardIdx = -1;
obstacleNum = 0;
//next Col
for(c = col+1; c < input[0].length; c++){
if(input[row][c].equals("G")){
guardIdx = c;
break;
}
if(input[row][c].equals("#")){
obstacleNum++;
}
}
if(guardIdx > 0){
colDistance = Math.min(colDistance, guardIdx-col-obstacleNum);
}
int distance = Math.min(rowDistance, colDistance);
return String.valueOf(distance);
}
Doesn't work for all cases. Change the guard position from (2,0) to (2,1) or (2,2) and it gives incorrect distances.
@Joe
Thanks for letting me know the error.
I fixed the error.
public static void main(String[] args){
//test data
String[][] input = {{".", "#", ".", "G", "."},
{".", ".", "#", ".", "."},
{".", "G", ".", ".", "."},
{".", ".", "#", ".", "."}};
// print the initial matrix
printInput(input);
// get distance matrix
getDistanceMatrix(input);
// print the distance matrix
printInput(input);
}
/**
* print for test
*/
static void printInput(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
System.out.print(input[row][col]);
if(col == input[0].length-1){
System.out.print("\n");
}
}
}
}
/**
* convert from the initial matrix to the distance matrix
* - each positions of Guard are start point
* @param input
*/
static void getDistanceMatrix(String[][] input){
HashMap<String, Integer> cache = new HashMap<String, Integer>();
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
if(input[row][col].equals("G")){
setDistance(input, row, col, 0, cache);
}
}
}
}
/**
* set the distance value of each position
*
* @param input
* @param row
* @param col
* @param distance
* @param cache
*/
static void setDistance(String[][] input, int row, int col, int distance, HashMap<String, Integer> cache){
if(row < 0 || col < 0 || row >= input.length || col >= input[0].length || input[row][col].equals("#")){
return;
}
String key = row+","+col;
if(cache.containsKey(key) && distance >= cache.get(key)){
return;
}
if(input[row][col].equals(".") || (!input[row][col].equals("#") && !input[row][col].equals("G"))){ // number
distance = getMinDistance(input, row, col, distance);
input[row][col] = String.valueOf(distance);
cache.put(key, Integer.parseInt(input[row][col]));
}else{
cache.put(key, 0);
}
if(!input[row][col].equals("#")){
distance++;
}
setDistance(input, row, col-1, distance, cache);
setDistance(input, row-1, col, distance, cache);
setDistance(input, row, col+1, distance, cache);
setDistance(input, row+1, col, distance, cache);
}
/**
* Find minimum distance from top, bottom, left and right
*
* @param input
* @param row
* @param col
* @param distance
* @return
*/
static int getMinDistance(String[][] input, int row, int col, int distance){
int MAX = Integer.MAX_VALUE;
int top = MAX;
int bottom = MAX;
int left = MAX;
int right = MAX;
//get top value of G
if(row > 0){
int r = row-1;
while(r >= 0){
if(input[r][col].equals("G")){
top = 1;
break;
}else if(input[r][col].equals("#")){
r--;
}else if(input[r][col].equals(".")){
break;
}else{
top = Integer.parseInt(input[r][col])+1;
break;
}
}
if(distance > top){
distance = top;
}
}
// get bottom value of G
if(row < input.length){
int r = row+1;
while(r <= input.length-1){
if(input[r][col].equals("G")){
bottom = 1;
break;
}else if(input[r][col].equals("#")){
r++;
}else if(input[r][col].equals(".")){
break;
}else{
bottom = Integer.parseInt(input[r][col])+1;
break;
}
}
if(distance > bottom){
distance = bottom;
}
}
// get left value of G
if(col > 0){
int c = col-1;
while(c >= 0){
if(input[row][c].equals("G")){
left = 1;
break;
}else if(input[row][c].equals("#")){
c--;
}else if(input[row][c].equals(".")){
break;
}else{
left = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > left){
distance = left;
}
}
// get right value of G
if(col < input[0].length){
int c = col+1;
while(c <= input[0].length-1){
if(input[row][c].equals("G")){
right = 1;
break;
}else if(input[row][c].equals("#")){
c++;
}else if(input[row][c].equals(".")){
break;
}else{
right = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > right){
distance = right;
}
}
return distance;
}
@Joe
Thanks.
I fixed the error.
I use recursive method from guard position.
public static void main(String[] args){
//test data
String[][] input = {{".", "#", ".", "G", "."},
{".", ".", "#", ".", "."},
{".", "G", ".", ".", "."},
{".", ".", "#", ".", "."}};
// print the initial matrix
printInput(input);
// get distance matrix
getDistanceMatrix(input);
// print the distance matrix
printInput(input);
}
/**
* print for test
*/
static void printInput(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
System.out.print(input[row][col]);
if(col == input[0].length-1){
System.out.print("\n");
}
}
}
}
/**
* convert from the initial matrix to the distance matrix
* - each positions of Guard are start point
* @param input
*/
static void getDistanceMatrix(String[][] input){
HashMap<String, Integer> cache = new HashMap<String, Integer>();
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
if(input[row][col].equals("G")){
setDistance(input, row, col, 0, cache);
}
}
}
}
/**
* set the distance value of each position
*
* @param input
* @param row
* @param col
* @param distance
* @param cache
*/
static void setDistance(String[][] input, int row, int col, int distance, HashMap<String, Integer> cache){
if(row < 0 || col < 0 || row >= input.length || col >= input[0].length || input[row][col].equals("#")){
return;
}
String key = row+","+col;
if(cache.containsKey(key) && distance >= cache.get(key)){
return;
}
if(input[row][col].equals(".") || (!input[row][col].equals("#") && !input[row][col].equals("G"))){ // number
distance = getMinDistance(input, row, col, distance);
input[row][col] = String.valueOf(distance);
cache.put(key, Integer.parseInt(input[row][col]));
}else{
cache.put(key, 0);
}
if(!input[row][col].equals("#")){
distance++;
}
setDistance(input, row, col-1, distance, cache);
setDistance(input, row-1, col, distance, cache);
setDistance(input, row, col+1, distance, cache);
setDistance(input, row+1, col, distance, cache);
}
/**
* Find minimum distance from top, bottom, left and right
*
* @param input
* @param row
* @param col
* @param distance
* @return
*/
static int getMinDistance(String[][] input, int row, int col, int distance){
int MAX = Integer.MAX_VALUE;
int top = MAX;
int bottom = MAX;
int left = MAX;
int right = MAX;
//get top value of G
if(row > 0){
int r = row-1;
while(r >= 0){
if(input[r][col].equals("G")){
top = 1;
break;
}else if(input[r][col].equals("#")){
r--;
}else if(input[r][col].equals(".")){
break;
}else{
top = Integer.parseInt(input[r][col])+1;
break;
}
}
if(distance > top){
distance = top;
}
}
// get bottom value of G
if(row < input.length){
int r = row+1;
while(r <= input.length-1){
if(input[r][col].equals("G")){
bottom = 1;
break;
}else if(input[r][col].equals("#")){
r++;
}else if(input[r][col].equals(".")){
break;
}else{
bottom = Integer.parseInt(input[r][col])+1;
break;
}
}
if(distance > bottom){
distance = bottom;
}
}
// get left value of G
if(col > 0){
int c = col-1;
while(c >= 0){
if(input[row][c].equals("G")){
left = 1;
break;
}else if(input[row][c].equals("#")){
c--;
}else if(input[row][c].equals(".")){
break;
}else{
left = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > left){
distance = left;
}
}
// get right value of G
if(col < input[0].length){
int c = col+1;
while(c <= input[0].length-1){
if(input[row][c].equals("G")){
right = 1;
break;
}else if(input[row][c].equals("#")){
c++;
}else if(input[row][c].equals(".")){
break;
}else{
right = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > right){
distance = right;
}
}
return distance;
}
void findGuardDistances(Museum museum) {
Queue<Record> queue = new LinkedList<>();
for (int x = 0; x < museum.width(); x++) {
for (int y = 0; y < museum.height(); y++) {
if (museum.cellAt(x, y) instanceof Guard) {
queue.add(new Record(x, y, 0));
}
}
}
while (!queue.isEmpty()) {
Record record = queue.poll();
int nextDistance = record.distance() + 1;
for (Neighbour n : Neighbour.values()) {
int nx = record.x() + n.dx();
int ny = record.y() + n.dy();
if (museum.cellAt(nx, ny) instanceof EmptySpace) {
museum.set(nx, ny, new GuardDistance(nextDistance));
queue.add(new Record(nx, ny, nextDistance));
}
}
}
}
I decided to receive the input as an array of open space nodes.
{{
def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()
MAX = 10000000
class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard
def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1
# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard
a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)
nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)
}}
I decided to receive the input as an array of open space nodes.
{{
def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()
MAX = 10000000
class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard
def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1
# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard
a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)
nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)
}}
I decided to receive the input as an array of open space nodes.
def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()
MAX = 10000000
class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard
def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1
# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard
a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)
nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)
// Simple BFS
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};
vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));
struct Vertex
{
int x;
int y;
Vertex(int x, int y): x(x), y(y) { }
};
vector<Vertex> getAdjacent(const Vertex& v)
{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));
return a;
}
void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;
q.push(v);
visited[v.x][v.y] = true;
int len = 0;
int levelCount = q.size();
while (q.size())
{
Vertex v = q.front();
q.pop();
if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;
vector<Vertex> a = getAdjacent(v);
for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}
--levelCount;
if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}
int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));
// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}
}
// Simple BFS
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};
vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));
struct Vertex
{
int x;
int y;
Vertex(int x, int y): x(x), y(y) { }
};
vector<Vertex> getAdjacent(const Vertex& v)
{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));
return a;
}
void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;
q.push(v);
visited[v.x][v.y] = true;
int len = 0;
int levelCount = q.size();
while (q.size())
{
Vertex v = q.front();
q.pop();
if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;
vector<Vertex> a = getAdjacent(v);
for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}
--levelCount;
if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}
int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));
// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}
}
// Simple BFS
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};
vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));
struct Vertex
{
int x;
int y;
Vertex(int x, int y): x(x), y(y) { }
};
vector<Vertex> getAdjacent(const Vertex& v)
{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));
return a;
}
void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;
q.push(v);
visited[v.x][v.y] = true;
int len = 0;
int levelCount = q.size();
while (q.size())
{
Vertex v = q.front();
q.pop();
if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;
vector<Vertex> a = getAdjacent(v);
for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}
--levelCount;
if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}
int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));
// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}
}
const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};
vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));
struct Vertex
{
int x;
int y;
Vertex(int x, int y): x(x), y(y) { }
};
vector<Vertex> getAdjacent(const Vertex& v)
{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));
return a;
}
void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;
q.push(v);
visited[v.x][v.y] = true;
int len = 0;
int levelCount = q.size();
while (q.size())
{
Vertex v = q.front();
q.pop();
if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;
vector<Vertex> a = getAdjacent(v);
for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}
--levelCount;
if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}
int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));
// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}
}
const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};
vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));
struct Vertex
{
int x;
int y;
Vertex(int x, int y): x(x), y(y) { }
};
vector<Vertex> getAdjacent(const Vertex& v)
{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));
return a;
}
void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;
q.push(v);
visited[v.x][v.y] = true;
int len = 0;
int levelCount = q.size();
while (q.size())
{
Vertex v = q.front();
q.pop();
if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;
vector<Vertex> a = getAdjacent(v);
for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}
--levelCount;
if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}
int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));
// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}
}
It is a great question. In order to solve it, we have to make a Breath First Search from every guard until we reach every floor cell in the maze then we can merge the matrix of every guard by taking the minimum distance. This is my complete implementation with the expected output.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class MazeScanner {
public static char[][] space = {
{'.', '#', '.', 'G', '.' },
{'.', '.', '#', '.', '.' },
{'G', '.', '.', '.', '.' },
{'.', '.', '#', '.', '.' },
};
static class Position {
int x;
int y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Position)) {
return false;
}
Position pos = (Position) obj;
if (this.x == pos.x && this.y == pos.y) {
return true;
}
return false;
}
@Override
public String toString() {
return "(" + x + ", " + y + ")";
}
}
public static Integer[][] solveMaze(char[][] space, Position guard) {
Integer[][] output = new Integer[space.length][space[0].length];
List<Position> visited = new ArrayList<>();
for (int i = 0; i < output.length; ++i) {
for (int j = 0; j < output[0].length; ++j) {
output[i][j] = -1;
}
}
Queue<Position> queue = new LinkedList<>();
output[guard.x][guard.y] = 0;
queue.add(guard);
while (! queue.isEmpty()) {
Position position = queue.poll();
if (output[position.x][position.y] == -1) {
Integer value = getNearestValue(output, position.x, position.y);
output[position.x][position.y] = value + 1;
}
List<Position> positions = getPossibleNeighours(space, position, visited);
if (positions.size() >= 1) {
queue.addAll(positions);
visited.addAll(positions);
}
}
return output;
}
public static String[][] solveMaze(char[][] space, Position[] guards) {
Integer[][] output = new Integer[space.length][space[0].length];
List<Integer[][]> possibleSolutions = new ArrayList<>();
for (int i = 0; i < guards.length; ++i) {
Integer[][] out = solveMaze(space, guards[i]);
//print2DArray(out);
possibleSolutions.add(out);
}
for (int i = 0; i < output.length; ++i) {
for (int j = 0; j < output[0].length; ++j) {
int minimumPositive = Integer.MAX_VALUE;
for (int z = 0; z < possibleSolutions.size(); ++z) {
if (possibleSolutions.get(z)[i][j] < minimumPositive && possibleSolutions.get(z)[i][j] > 0) {
minimumPositive = possibleSolutions.get(z)[i][j];
}
}
if (minimumPositive != Integer.MAX_VALUE) {
output[i][j] = minimumPositive;
} else {
output[i][j] = -1;
}
}
}
String[][] finalOutput = new String[space.length][space[0].length];
for (int i = 0; i < finalOutput.length; ++i) {
for (int j = 0; j < finalOutput[0].length; ++j) {
if (output[i][j] > 0 && space[i][j] != 'G' && space[i][j] != '#') {
finalOutput[i][j] = output[i][j] + "";
} else {
finalOutput[i][j] = space[i][j] + "";
}
}
}
return finalOutput;
}
private static Integer getNearestValue(Integer[][] output, Integer x, Integer y) {
if (x + 1 <= output.length - 1 && output[x + 1][y] != -1) {
return output[x + 1][y];
}
if (x - 1 >= 0 && output[x - 1][y] != -1) {
return output[x - 1][y];
}
if (y + 1 <= output[0].length - 1 && output[x][y + 1] != -1) {
return output[x][y + 1];
}
if (y - 1 >= 0 && output[x][y - 1] != -1) {
return output[x][y - 1];
}
throw new RuntimeException("[Severe] cannot get a nearest value ...");
}
private static List<Position> getPossibleNeighours(char[][] space, Position position, List<Position> visited) {
int x = position.x;
int y = position.y;
List<Position> positions = new ArrayList<>();
if (x + 1 <= space.length - 1 && space[x + 1][y] != '#' && space[x + 1][y] != 'G') {
Position pos = new Position(x + 1, y);
if (! visited.contains(pos)) {
positions.add(pos);
}
}
if (x - 1 >= 0 && space[x - 1][y] != -1 && space[x - 1][y] != '#' && space[x - 1][y] != 'G') {
Position pos = new Position(x - 1, y);
if (! visited.contains(pos)) {
positions.add(pos);
}
}
if (y + 1 <= space[0].length - 1 && space[x][y + 1] != -1 && space[x][y + 1] != '#' && space[x][y + 1] != 'G') {
Position pos = new Position(x, y + 1);
if (! visited.contains(pos)) {
positions.add(pos);
}
}
if (y - 1 >= 0 && space[x][y - 1] != -1 && space[x][y - 1] != '#' && space[x][y - 1] != 'G') {
Position pos = new Position(x, y - 1);
if (! visited.contains(pos)) {
positions.add(pos);
}
}
return positions;
}
public static void main(String[] args) {
Position[] positions = new Position[] {
new Position(2, 0),
new Position(0, 3)
};
String[][] output = solveMaze(space, positions);
print2DArray(output);
}
public static<T> void print2DArray (T[][] output) {
for (int i = 0; i < output.length; ++i) {
for (int j = 0; j < output[0].length; ++j) {
System.out.print(output[i][j] + " ");
}
System.out.println(" ");
}
}
}
i think we can save ourself from doing BFS on N nodes. Here is what i propose:-
(1) first traverse the whole array and while traversing whenever you find a G, we turn all the accessible points from that G with distance of 1 only as 1, i.e. the immediate n, s, e, w points to this G as 1. and keep putting these cells in a queue.
(2) while the queue is not empty, we pop one element (one cell) and turn it's n, s, e, w to be min(it's neighbors + 1); and put this new cell in queue.
NOTE: since not all the neighbors are having the value we just take those that have and we shall check this value again. Also the cells that have value as 1 cannot be better than that so we don't enqueue them again.
Please reply if you find any ambiguity in the algorithm.
I was looking at this question for long time waiting for a good answer to come! (I posted this question). The best algorithm for this problem is of O(nlogn). it gets implemented using shortest path algorithm (Dijkstra). The famous algorithm should be modified slightly as follows:
1. in the beginning, all of the guard locations can be starting point. Therefore, instead of just adding one point to the main heap in the code, we add all of the guard locations to that heap with distance of 0.
2. Instead of ending the algorithm when destination is met, the algorithm ends when the main heap is empty, meaning all of the locations are met.
With these modifications, Dijkstra algorithm with O(nlogn) can solve it.
Hi when you say a Dijkstra's algorithm, how would you do that since it is possible only in a directed graph and this is not.... because if we are able to go from arr[i][j] to arr[i-1][j] then reverse is also true... Please correct me if I am wrong. Moreover when you say you would use HEAP DS then do you intend to change the structure of Heap DS as a node can have 2 children but in this question a node can have 4 immediate children (n, s, e, w);
This is the answer I wrote in my interview. This algorithm works for many cases but it is wrong. It can produce wrong results. The logic to explain why it is wrong is very complex and unfortunately I don't have time to explain it. One of my Googler friends told me why it was wrong. Even the interviewer told me I solved it right and he did not realize the logic error while I was writing the code.
Anyways I write the code I gave in my interview here. FYI, I didn't get the offer. So this code is not good enough eventhough it works for many cases.
class Pairs {
int MAXCOL = 1000;
private int row;
private int col;
pubic Pairs(int r, int c) {
row = r;
col = c;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public boolean isEqual(Pairs p) {
return (this.row == p.row && this.col == p.row);
}
public int hashCode() {
return row * MAXCOL + col;
}
}
class Museum {
List<Pairs> obstacles;
List<Pairs> guards;
int rowSize;
int colSize;
public Museum(List<Pairs> o, List<Pairs> g, int row, int col) {
obstacles = o;
guards = g;
rowSize = row;
colSize = col;
//There should be checking that all the pairs inside o and g are within map
//...
}
public Map<Pairs, Integer> getGuardDistance() {
//First create a queue of all the empty spaces
Queue<Pairs> notFilinzed = new LinkedList<>();
Map<Pairs, Integer> distances = new HashMap<>();
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize; j++) {
Pairs p = new Pairs(i, j);
if ((!obstacles.contains(p)) && (!guards.contains(p))) {
notFilinzed.add(p);
distances.put(p, Integer.MAX_VALUE);
}
if (guards.contains(p)) {
distances.put(p, 0);
}
if (obstacles.contains(p)) {
distances.put(p, Integer.MAX_VALUE);
}
}
}
//as long as I have something in the que
while (!notFilinzed.isEmpty()) {
Pair p = notFilinzed.poll();
int min = Integer.MAX_VALUE;
boolean foundDistance = false;
//top:
if (p.row - 1 >= 0) {
Pairs top = new Pairs(p.row - 1, p.col);
if (!notFilinzed.contains(top) && !obstacles.contains(top) && distances.get(top) < min) {
min = distances.get(top);
foundDistance = true;
}
}
//right
if (p.col + 1 < colSize) {
Pairs right = new Pairs(p.row, p.col + 1);
if (!notFilinzed.contains(right) && !obstacles.contains(right) && distances.get(right) < min) {
min = distances.get(right);
foundDistance = true;
}
}
//bottom
if (p.row < rowSize) {
Pairs bottom = new Pairs(p.row + 1, p.col);
if (!notFilinzed.contains(bottom) && !obstacles.contains(bottom) && distances.get(bottom) < min) {
min = distances.get(bottom);
foundDistance = true;
}
}
//left
if (p.col - 1 >= 0) {
Pairs left = new Pairs(p.row, p.col - 1);
if (!notFilinzed.contains(left) && !obstacles.contains(left) && distances.get(left) < min) {
min = distances.get(left);
foundDistance = true;
}
}
if (!foundDistance) {
notFilinzed.add(p);
}
distances.put(p, min + 1);
}
//Create output format
return distances;
}
}
Hello amirtar,
This is the code that i wrote. It has a slight modification of saving the best path once i reach a guard and the path i took to reach that guard. This way i save myself from doing a BFS on all nodes.
package arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class GuardEmptySpace {
/*char[][] museum = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}
};*/
char[][] museum = {
{'.', '.', '.', 'G'},
{'.', '.', '.', '.'},
{'G', '#', '#', '.'},
{'.', 'G', '#', '.'}
};
int[][] space = new int[museum.length][museum[0].length];
Queue<String> q;
Set<String> set;
public static void main(String[] args) {
GuardEmptySpace ges = new GuardEmptySpace();
ges.findSpace();
}
private void findSpace() {
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
if (museum[i][j] == 'G') {
//set n, s, e, w to be accessible in just one unit of space if they are not having #
setSpace(i, j);
space[i][j] = Integer.MIN_VALUE;
} else if (museum[i][j] == '#') {
space[i][j] = Integer.MAX_VALUE;
}
}
}
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
q = new LinkedList<String>();
set = new HashSet<String>();
if (space[i][j] == 0) {
set.add(i + "," + j);
q.add(i + "," + j);
setPath(performBFS());
}
}
}
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
if (space[i][j] == Integer.MIN_VALUE) {
System.out.print("G");
} else if (space[i][j] == Integer.MAX_VALUE) {
System.out.print("#");
} else {
System.out.print(space[i][j]);
}
}
System.out.println();
}
}
private void setPath(String s) {
String[] split = s.split(";");
int k = 1;
for (int i = split.length - 2; i >= 0; i--, k++) {
String[] split2 = split[i].split(",");
space[Integer.parseInt(split2[0])][Integer.parseInt(split2[1])] = k;
}
}
private String performBFS() {
int i, j;
while (!q.isEmpty()) {
StringBuilder sb = new StringBuilder(q.poll());
String str = getIndexString(sb.toString());
String[] split = str.split(",");
i = Integer.parseInt(split[0]);
j = Integer.parseInt(split[1]);
if (museum[i][j] == 'G') {
return sb.toString();
} else {
changeQueue(sb.toString(), i - 1, j);
changeQueue(sb.toString(), i + 1, j);
changeQueue(sb.toString(), i, j - 1);
changeQueue(sb.toString(), i, j + 1);
}
}
return "";
}
private void changeQueue(String str, int i, int j) {
StringBuilder sb = new StringBuilder(str);
if (isGoodCell(i, j)) {
q.add(sb.append(";").append(i).append(",").append(j).toString());
set.add(i + "," + j);
}
}
private String getIndexString(String str) {
String[] split = str.split(";");
int size = split.length;
return split[size - 1];
}
private boolean isGoodCell(int i, int j) {
if ((i < museum.length && i >= 0) && (j < museum[0].length && j >= 0)) {
if ((!set.contains(i + "," + j)) && (space[i][j] != Integer.MAX_VALUE)) {
return true;
}
}
return false;
}
private void setSpace(int i, int j) {
// set north
if ((i - 1 >= 0) && (space[i - 1][j] != '#')) {
space[i - 1][j] = 1;
}
// set south
if ((i + 1 < museum.length) && (space[i + 1][j] != '#')) {
space[i + 1][j] = 1;
}
//set east
if ((j - 1 >= 0) && (space[i][j - 1] != '#')) {
space[i][j - 1] = 1;
}
if ((j + 1 < museum[0].length) && (space[i][j + 1] != '#')) {
space[i][j + 1] = 1;
}
}
}
Hello Madhur, your code does not seem to have the error I thought. I tested a couple of cases I thought may produce bug, but it didn't. Unfortunately, I could not read your code. I think you need to use data structures rather than passing i and j as string and then parsing them back to integer. This does not seem like a good policy if you are doing job interview and makes the code harder to read.
This question is a simple modification of dijkstra. i.e with multiple sources. Complexity would be the same as v^2, that is in this case (n*m)^2.
struct node
{
int val;
int i;
int j;
node(int val_, int l_, int r_) :val(val_), i(l_), j(r_){}
};
class comparator
{
public:
bool operator() (node n1, node n2)
{
return n1.val > n2.val;
}
};
void fillmap(int n, int m, char arry[6][5])
{
priority_queue<node, vector<node>, comparator> pq;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (arry[i][j] == 'G')arry[i][j] = 0;
//if (arry[i][j] == '#')arry[i][j] = CHAR_MAX;
if (arry[i][j] == '.')arry[i][j] = CHAR_MAX;
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (arry[i][j] == 0)pq.push(node(0, i, j));
}
}
while (!pq.empty())
{
node nd = pq.top();
pq.pop();
if (nd.i - 1 >= 0 && arry[nd.i - 1][nd.j] != '#' && arry[nd.i - 1][nd.j] > arry[nd.i][nd.j] + 1)
{
arry[nd.i - 1][nd.j] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i - 1, nd.j));
}
if (nd.i + 1 != n && arry[nd.i + 1][nd.j] != '#' && arry[nd.i + 1][nd.j] > arry[nd.i][nd.j] + 1)
{
arry[nd.i + 1][nd.j] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i + 1, nd.j));
}
if (nd.j - 1 >= 0 && arry[nd.i][nd.j - 1] != '#' && arry[nd.i][nd.j - 1] > arry[nd.i][nd.j] + 1)
{
arry[nd.i][nd.j - 1] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i, nd.j - 1));
}
if (nd.j + 1 != m && arry[nd.i][nd.j + 1] != '#' && arry[nd.i][nd.j + 1] > arry[nd.i][nd.j] + 1)
{
arry[nd.i][nd.j + 1] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i, nd.j + 1));
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cout << (int)arry[i][j] << " ";
}
cout << endl;
}
}
My general idea takes principles from Dijkstra's algorithm and backtracking.
We essentially backtrack from all guards, setting distances of surrounding free cells to 1.
Whenever a distance gets 'relaxed' (see Dijkstra), update distances of surrounding free cells if they would be reduced. This cascading effect will continue for each guard until no cells can be relaxed any further. At this point, you end up with the min distances for each empty space to some guard.
Ex:
- Create 2D array R to hold results, initially setting all distances to infinity
- For each location L in input matrix M
If M[L] is 'G', for each direction D (up/down/left/right), if M[D] is '.' and R[D] > 1, R[D] = 1 and recurse on D
If M[L] is '.', for each direction D, if M[D] is '.' and R[D] > R[L] + 1, R[D] = R[L] + 1 and recurse on D
Keep the data in a 2d array of ints where it can be a pseudo graph. Then complete a DFS from each position to the Guard using previous computations to short circuit the computations.
public static final int WALL=Integer.MAX_VALUE;
public static final int UNCHECKED = -2;
public static final int OPEN = -1;
public static final int GUARD = 0;
public static void computeDistance(int[][] room){
class Worker{
int[][] area;
int[][] results;
private Worker(int[][] area, int[][] results){
this.area = area;
this.results = new int[area.length][area[0].length];
for(int y = 0; y < this.area.length; y++){
for(int x = 0; x < this.area[0].length; x++){
this.results[y][x] =UNCHECKED;
}
}
}
private void work(){
for(int y = 0; y < this.area.length; y++){
for(int x = 0; x < this.area[0].length; x++){
this.work(x, y);
}
}
}
private int work(int x, int y){
if(y < 0 || y > this.area.length){
return WALL;
}
if(x < 0 || x > this.area[0].length){
return WALL;
}
int returnVal = this.results[y][x];
if(returnVal != UNCHECKED){
return returnVal ;
}
int areaVal = this.area[y][x];
if(areaVal == WALL){
returnVal = WALL;
}
else if(areaVal == GUARD){
returnVal = GUARD;
}
else if(areaVal == OPEN){
returnVal = Math.min(work(x, y+1), Math.min(x+1, y, Math.min(work(x, y-1), work(x-1, y))));
if(returnVal == WALL){
returnVal = OPEN;
}
else if(returnVal < WALL && returnVal > OPEN){
returnVal++;
}
}
this.results[y][x] = returnVal;
return returnVal;
}
}
Worker worker = new Worker(room);
worker.work();
return worker.results;
}
public class HelloWorld{
public static void main(String []args){
char input[][]= {{'.','#','.','G','.'}, {'.','.','#','.','.'}, {'G','.','.','.','.'}, {'.','.','#','.','.'}} ;
char[][] result= f(input);
for(int i=0; i<result.length; i++){
for(int j=0; j<result[0].length; j++){
System.out.print(result[i][j]+" ");
}
System.out.println();
}
}
public static char[][] f(char[][] arr){
int m= arr.length;
int n= arr[0].length;
char[][] buff= new char[m][n];
int[][] A= new int[m][n];
int tcount=0; // count for replaced cells
//convert arr to A -- 1 <-- G , Integer.MAX_VALUE/2 <-- #
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(arr[i][j]=='G'){
A[i][j]=1;
tcount++;
}
else if(arr[i][j]=='#'){
A[i][j]= Integer.MAX_VALUE/2;
tcount++;
}
}
}
f1(A, tcount);
//convert A to buff -- 1 --> G , Integer.MAX_VALUE/2 --> #, any no. i --> i-1
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(A[i][j]==1){
buff[i][j]='G';
}
else if(A[i][j]==Integer.MAX_VALUE/2){
buff[i][j]= '#';
}
else{
int val=A[i][j];
buff[i][j]= Character.forDigit(val-1, 10);
}
}
}
return buff;
}
private static void f1(int[][] A, int tcount){
int m= A.length;
int n= A[0].length;
int minVal=1;
while(tcount<m*n){
int temp=minVal;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(A[i][j]==minVal){
if(i>0 && A[i][j]==minVal && A[i-1][j]==0){
A[i-1][j]=minVal+1;
temp=minVal+1;
tcount++;
}
if(i<m-1 && A[i][j]==minVal && A[i+1][j]==0){
A[i+1][j]=minVal+1;
temp=minVal+1;
tcount++;
}
if(j<n-1 && A[i][j]==minVal && A[i][j+1]==0){
A[i][j+1]=minVal+1;
temp=minVal+1;
tcount++;
}
if(j>0 && A[i][j]==minVal && A[i][j-1]==0){
A[i][j-1]=minVal+1;
temp=minVal+1;
tcount++;
}
}
}
}
//System.out.println(tcount);
minVal= Math.max(temp, minVal);
}
}
}
Basically doing BFS from each guard and updating only if the distance is better than the distance at that cell (no need for a hash table)
package guards;
import java.util.LinkedList;
public class guards {
public static final int G = 0;
public static final int $ = -1;
public static final int _ = Integer.MAX_VALUE;
public static void fillSpaces(int[][] mat) {
LinkedList<Tuple2> v = new LinkedList<Tuple2>();
for(int i=0;i<mat.length;i++) {
for(int k=0;k<mat[0].length;k++) {
if(mat[i][k]==G) {
v.add(new Tuple2(i,k));
}
}
}
while(!v.isEmpty()) {
Tuple2 node = v.remove();
v.addAll(getNeighbors(node,mat));
}
}
private static LinkedList<Tuple2> getNeighbors(Tuple2 node, int[][] mat) {
int i=node.A;
int k=node.B,dist = mat[i][k]+1;
int[] y = {i-1,i+1,i,i};
int[] x = {k,k,k-1,k+1};
LinkedList<Tuple2> adj = new LinkedList<Tuple2>();
for(int m=0;m<x.length;m++) {
if(x[m]>=0&&y[m]>=0&&x[m]<mat[0].length&&y[m]<mat.length) {
if(mat[y[m]][x[m]]>0&&mat[y[m]][x[m]]>dist) {
mat[y[m]][x[m]] = dist;
adj.add(new Tuple2(y[m],x[m]));
}
}
}
return adj;
}
public static void main(String[] args) {
int[][] floor = {
{_,$,_,G,_},
{_,_,$,_,_},
{G,_,_,_,_},
{_,_,$,_,_}
};
fillSpaces(floor);
for(int i=0;i<floor.length;i++) {
for(int k=0;k<floor[0].length;k++) {
if(floor[i][k] == G) {
System.out.print("G,");
} else if(floor[i][k] == $) {
System.out.print("#,");
} else {
System.out.print(floor[i][k]+",");
}
}
System.out.print("\n");
}
}
}
Simple solution. Once you understand the logic, you can apply to many other problems by
doing some minor changes. (e.g. Maze, Knights Movement, N-Queen, Sudoku etc.)
import java.util.Arrays;
public class MuseumGuardian {
static int[] moveX = {0, 0, 1, -1};
static int[] moveY = {1, -1, 0, 0};
public static void main(String[] args) {
char[][] board =
{
{'.', '#', '.', 'G', 'G'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}
};
solve(board);
for (char[] arr : board) {
System.out.println(Arrays.toString(arr));
}
}
/// Helper Methods
static int atoi(char c) {
return c - '0';
}
static char itoa(int n) {
return (char)('0' + n);
}
public static void solve(char[][] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 'G') {
markNeighbors(A, i, j, 0);
}
}
}
}
public static boolean isSafe(char[][] A, int i, int j, int newValue) {
if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
return false;
}
if (A[i][j] == 'G' || A[i][j] == '#') {
return false;
}
if (A[i][j] != '.' && atoi(A[i][j]) <= newValue) {
return false;
}
return true;
}
public static void markNeighbors(char[][] A, int i, int j, int value) {
for (int k = 0; k < moveX.length; k++) {
int nextX = i + moveX[k];
int nextY = j + moveY[k];
if (isSafe(A, nextX, nextY, value + 1)) {
A[nextX][nextY] = itoa(value + 1);
markNeighbors(A, nextX, nextY, value + 1);
}
}
}
}
This will do it (a graph solution). The idea is to present each element of array as Node with information of its children. Each node will have a computed "cost" this is simply a minimum distance from Node to Guard.
import java.util.ArrayList;
import java.util.List;
/**
* @author Yura Tkachenko
*/
public class GTask1 {
public class Node {
private int cost;
private boolean computedCost;
private boolean guard;
private boolean obstacle;
private boolean lock;
private int maxThreshold;
private List<Node> children = new ArrayList<Node>();
public Node(String initializer) {
if ("#".equalsIgnoreCase(initializer)) {
setObstacle(true);
} else if ("G".equalsIgnoreCase(initializer)) {
setGuard(true);
}
}
public int getMaxThreshold() {
return maxThreshold;
}
public void setMaxThreshold(int maxThreshold) {
this.maxThreshold = maxThreshold;
}
public void addChild(Node n) {
children.add(n);
}
public boolean isLock() {
return lock;
}
public void setLock(boolean lock) {
this.lock = lock;
}
public int getCost() {
return cost;
}
public void setCost(int cost) {
this.cost = cost;
}
public boolean isComputedCost() {
return computedCost;
}
public void setComputedCost(boolean computedCost) {
this.computedCost = computedCost;
}
public boolean isGuard() {
return guard;
}
public void setGuard(boolean guard) {
this.guard = guard;
}
public boolean isObstacle() {
return obstacle;
}
public void setObstacle(boolean obstacle) {
this.obstacle = obstacle;
}
public void computeCost() {
int k = getMaxThreshold();
if (isComputedCost() || isLock()) {
return;
}
setLock(true);
// find if any children is G or has cost of 1
for (Node child : children) {
if (child.isGuard()) {
k = 1;
break;
}
if (child.isObstacle() || child.isLock()) {
continue;
}
if (!child.isComputedCost()) {
child.computeCost();
}
if (child.isComputedCost()) {
k = Math.min(k, child.getCost()+1);
}
}
setCost(k);
setComputedCost(true);
setLock(false);
}
public void balanceCost() {
for (Node child : children) {
if (!isGuard() || !isObstacle()) {
child.setCost(Math.min(getCost() + 1, child.getCost()));
}
}
}
@Override
public String toString() {
if (isGuard()) {
return "G";
} else if (isObstacle()) {
return "#";
} else if (!isComputedCost()){
return ".";
} else {
return String.valueOf(getCost());
}
}
}
public Node[] convertAdjList(String[][] input) {
List<Node> nodes = new ArrayList<Node>();
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
nodes.add(new Node(input[i][j]));
}
}
// set children
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
int currentIndex = i*input[0].length+j;
int leftIndex = currentIndex-1;
int rightIndex = currentIndex+1;
int topIndex = currentIndex - input[0].length;
int bottomIndex = currentIndex + input[0].length;
Node currentNode = nodes.get(currentIndex);
currentNode.setMaxThreshold(nodes.size());
if (leftIndex >= i*input[0].length) {
currentNode.addChild(nodes.get(leftIndex));
}
if (rightIndex < (i+1)*input[0].length) {
currentNode.addChild(nodes.get(rightIndex));
}
if (topIndex >= 0) {
currentNode.addChild(nodes.get(topIndex));
}
if (bottomIndex < nodes.size()) {
currentNode.addChild(nodes.get(bottomIndex));
}
}
}
return nodes.toArray(new Node[nodes.size()]);
}
public static void main(String[] args) {
String[][] arr = new String[][] {
{".","#",".","G","."},
{".",".","#",".","."},
{"G",".",".",".","."},
{".",".","#",".","."}
};
GTask1 g = new GTask1();
Node[] nodes = g.convertAdjList(arr);
int i = 1;
String line = "";
for (Node node : nodes) {
node.computeCost();
}
for (Node node : nodes) {
node.balanceCost();
line += node.toString();
if (i % 5 == 0) {
System.out.println(line);
line = "";
}
i++;
}
System.out.println("End");
}
}
import java.util.ArrayList;
import java.util.List;
/**
* @author Yura Tkachenko
*/
public class GTask1 {
public class Node {
private int cost;
private boolean computedCost;
private boolean guard;
private boolean obstacle;
private boolean lock;
private int maxThreshold;
private List<Node> children = new ArrayList<Node>();
public Node(String initializer) {
if ("#".equalsIgnoreCase(initializer)) {
setObstacle(true);
} else if ("G".equalsIgnoreCase(initializer)) {
setGuard(true);
}
}
public int getMaxThreshold() {
return maxThreshold;
}
public void setMaxThreshold(int maxThreshold) {
this.maxThreshold = maxThreshold;
}
public void addChild(Node n) {
children.add(n);
}
public boolean isLock() {
return lock;
}
public void setLock(boolean lock) {
this.lock = lock;
}
public int getCost() {
return cost;
}
public void setCost(int cost) {
this.cost = cost;
}
public boolean isComputedCost() {
return computedCost;
}
public void setComputedCost(boolean computedCost) {
this.computedCost = computedCost;
}
public boolean isGuard() {
return guard;
}
public void setGuard(boolean guard) {
this.guard = guard;
}
public boolean isObstacle() {
return obstacle;
}
public void setObstacle(boolean obstacle) {
this.obstacle = obstacle;
}
public void computeCost() {
int k = getMaxThreshold();
if (isComputedCost() || isLock()) {
return;
}
setLock(true);
// find if any children is G or has cost of 1
for (Node child : children) {
if (child.isGuard()) {
k = 1;
break;
}
if (child.isObstacle() || child.isLock()) {
continue;
}
if (!child.isComputedCost()) {
child.computeCost();
}
if (child.isComputedCost()) {
k = Math.min(k, child.getCost()+1);
}
}
setCost(k);
setComputedCost(true);
setLock(false);
// balanceCost();
}
public void balanceCost() {
for (Node child : children) {
if (!isGuard() || !isObstacle()) {
child.setCost(Math.min(getCost() + 1, child.getCost()));
}
}
}
@Override
public String toString() {
if (isGuard()) {
return "G";
} else if (isObstacle()) {
return "#";
} else if (!isComputedCost()){
return ".";
} else {
return String.valueOf(getCost());
}
}
}
public Node[] convertAdjList(String[][] input) {
List<Node> nodes = new ArrayList<Node>();
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
nodes.add(new Node(input[i][j]));
}
}
// set children
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
int currentIndex = i*input[0].length+j;
int leftIndex = currentIndex-1;
int rightIndex = currentIndex+1;
int topIndex = currentIndex - input[0].length;
int bottomIndex = currentIndex + input[0].length;
Node currentNode = nodes.get(currentIndex);
currentNode.setMaxThreshold(nodes.size());
if (leftIndex >= i*input[0].length) {
currentNode.addChild(nodes.get(leftIndex));
}
if (rightIndex < (i+1)*input[0].length) {
currentNode.addChild(nodes.get(rightIndex));
}
if (topIndex >= 0) {
currentNode.addChild(nodes.get(topIndex));
}
if (bottomIndex < nodes.size()) {
currentNode.addChild(nodes.get(bottomIndex));
}
}
}
return nodes.toArray(new Node[nodes.size()]);
}
public static void main(String[] args) {
String[][] arr = new String[][] {
{".","#",".","G","."},
{".",".","#",".","."},
{"G",".",".",".","."},
{".",".","#",".","."}
};
GTask1 g = new GTask1();
Node[] nodes = g.convertAdjList(arr);
int i = 1;
String line = "";
for (Node node : nodes) {
node.computeCost();
}
for (Node node : nodes) {
node.balanceCost();
line += node.toString();
if (i % 5 == 0) {
System.out.println(line);
line = "";
}
i++;
}
System.out.println("End");
}
}
- Sergey May 06, 2015// Simple BFS #include <iostream> #include <queue> #include <vector> #include <string> using namespace std; const int X = 4; const int Y = 5; char const M[X][Y] = { {'.', '#', '.', 'G', '.'}, {'.', '.', '#', '.', '.'}, {'G', '.', '.', '.', '.'}, {'.', '.', '#', '.', '.'}, }; vector<vector<int>> LEN( X, std::vector<int>(Y, X + Y)); struct Vertex { int x; int y; Vertex(int x, int y): x(x), y(y) { } }; vector<Vertex> getAdjacent(const Vertex& v) { vector<Vertex> a; if (v.x + 1 < X && M[v.x + 1][v.y] != '#') a.push_back(Vertex(v.x + 1, v.y)); if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#') a.push_back(Vertex(v.x - 1, v.y)); if (v.y + 1 < Y && M[v.x][v.y + 1] != '#') a.push_back(Vertex(v.x, v.y + 1)); if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#') a.push_back(Vertex(v.x, v.y - 1)); return a; } void bfs(const Vertex& v) { bool visited[X][Y] = { false }; queue<Vertex> q; q.push(v); visited[v.x][v.y] = true; int len = 0; int levelCount = q.size(); while (q.size()) { Vertex v = q.front(); q.pop(); if (len < LEN[v.x][v.y]) LEN[v.x][v.y] = len; vector<Vertex> a = getAdjacent(v); for (unsigned i = 0; i != a.size(); ++i) { if (!visited[a[i].x][a[i].y]) { q.push(Vertex(a[i].x, a[i].y)); visited[a[i].x][a[i].y] = true; } } --levelCount; if (levelCount == 0) { ++len; levelCount = q.size(); } } } int main() { // Run BFS from each GUARD for (int i = 0; i != X; ++i) for (int j = 0; j != Y; ++j) if (M[i][j] == 'G') bfs(Vertex(i, j)); // Print the result for (int i = 0; i != X; ++i) { for (int j = 0; j != Y; ++j) { if (M[i][j] != 'G' && M[i][j] != '#') cout << LEN[i][j]; else cout << M[i][j]; } cout << endl; } }