Facebook Interview Question
Android EngineersCountry: United States
Interview Type: Phone Interview
search guards first and do BST on each guard. Note if the new distance is larger or equal to the previously calculated distance we can break. This way the time complexity can be kept at column x row.
#include <vector>
#include <list>
#include <iostream>
using namespace std;
enum {W = -2, G = -1, O = 0};
struct OpenSpace {
int x;
int y;
int distance;
};
void findGuard (const vector<vector<int>> & matrix, list<pair<int, int>> & guards) {
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
if (matrix[i][j] == G) {
guards.push_back({i, j});
}
}
}
}
void inspect(vector<vector<int>> & matrix, list<OpenSpace> & queue) {
int curX = queue.front().x, curY = queue.front().y;
int distance = queue.front().distance;
queue.pop_front();
int shift[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
for(int i = 0; i < 4; i++) {
int x = curX + shift[i][0];
int y = curY + shift[i][1];
if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()
&& matrix[x][y] != G && matrix[x][y] != W) {
if (matrix[x][y] == O || matrix[x][y] > distance + 1) {
matrix[x][y] = distance + 1;
queue.emplace_back(OpenSpace({x, y, distance+1}));
}
}
}
}
void findCoverage(vector<vector<int>> & matrix) {
list<pair<int, int>> guards;
findGuard(matrix, guards);
for (pair<int, int> xy : guards) {
list<OpenSpace> queue;
queue.emplace_back(OpenSpace({xy.first, xy.second, 0}));
// do BFS for each guard
while (!queue.empty()) {
inspect(matrix, queue);
}
}
}
int main() {
vector<vector<int>> matrix =
{{O, W, O, G, O},
{G, G, W, O, O},
{W, O, O, W, O},
{O, O, G, O, G}};
findCoverage(matrix);
for (auto row : matrix) {
for (auto i : row) {
printf("%2d ", i);
}
printf("\n");
}
}
My solution is a greedy algorithm that expands on every Guard cell updating neighbor distances, after that it does a top down and bottom-up expansion for updating open space cells. Time : O(n^2) space: O(n). Quite extensive code but it works.
public class MuseumDistances {
private static final int UNDISCOVERED = Integer.MAX_VALUE;
public static void main(String[] args) {
char[][] m = {{'O', 'W', 'G', 'O'},
{'O', 'W', 'W', 'O'},
{'O', 'W', 'O', 'O'},
{'O', 'O', 'O', 'G'}};
printMatrix(findDistanceMatrix(m));
char[][] m2 =
{
{'O', 'O', 'G', 'G', 'G'},
{'O', 'W', 'O', 'O', 'O'},
{'O', 'W', 'G', 'W', 'O'},
{'O', 'W', 'W', 'W', 'O'},
{'O', 'O', 'O', 'O', 'O'}};
printMatrix(findDistanceMatrix(m2));
}
public static int[][] findDistanceMatrix(char[][] m) {
int r[][] = new int[m.length][m.length];
// prepare distance matrix
for (int i = 0; i < r.length; i++) {
for (int j = 0; j < r.length; j++) {
if (m[i][j] == 'G') {
r[i][j] = 0;
} else if (m[i][j] == 'W') {
r[i][j] = -1;
} else {
r[i][j] = UNDISCOVERED;
}
}
}
// expand based on Guard cells
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m.length; j++) {
if (r[i][j] == 0) {
expandDistances(r, i, j);
}
}
}
// top down and bottom up sweep to update open cell neighbors
for (int i = m.length - 1; i >= 0; i--) {
for (int j = m.length - 1; j >= 0; j--) {
if (r[i][j] != 0 && r[i][j] != -1) {
expandDistancesNeighbors(r, i, j, false);
expandDistancesNeighbors(r, i, j, true);
}
}
}
return r;
}
private static void expandDistancesNeighbors(int[][] r, int x, int y, boolean rightDown) {
int i = x, j = y;
int dist = r[x][y];
if (rightDown) {
// expand down
i = x + 1;
while (i < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
i++;
}
// expand right
i = x;
j = y + 1;
dist = r[x][y];
while (j < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
j++;
}
} else {
// expand up
i = x - 1;
while (i >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
i--;
}
// expand left
i = x;
j = y - 1;
dist = r[x][y];
while (j >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
j--;
}
}
}
public static void printMatrix(int[][] a) {
for (int i = 0; i < a.length; i++) {
System.out.println();
for (int j = 0; j < a.length; j++) {
System.out.print(a[i][j] + " ");
}
}
}
public static void expandDistances(int[][] r, int x, int y) {
if (x >= r.length || y >= r.length || x < 0 || y < 0 || r[x][y] == -1) {
return;
} else {
int i = x, j = y;
int dist = 1;
// expand up
i = x - 1;
while (i >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
i--;
}
// expand down
i = x + 1;
dist = 1;
while (i < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
i++;
}
// expand right
i = x;
j = y + 1;
dist = 1;
while (j < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
j++;
}
// expand left
j = y - 1;
dist = 1;
while (j >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
j--;
}
}
}
}
The following code iterates over every entry in the matrix, and performs BFS outwards at each entry, returning the distance as soon as it encounters a guard entry.
from collections import deque
def guards(m):
d = empty_copy(m)
for i in range(0, len(m)):
for j in range(0, len(m[i])):
d[i][j] = guards_dist(m, i, j)
format(m, d)
return d
def empty_copy(m):
res = []
for i in range(0, len(m)):
res.append([])
for j in range(0, len(m[i])):
res[i].append(None)
return res
def format(m, d):
for i in range(0, len(m)):
for j in range(0, len(m[i])):
if m[i][j] == "G" or m[i][j] == "W":
d[i][j] = m[i][j]
else:
d[i][j] = str(d[i][j])
def guards_dist(m, i, j):
seen = {}
q = deque([(i, j, 0)])
while len(q) > 0:
i, j, dist = q.popleft()
if i < 0 or i >= len(m) or j < 0 or j >= len(m[i]) or (i, j) in seen:
continue
seen[(i, j)] = True
if m[i][j] == "G":
return dist
elif m[i][j] == "W":
continue
else:
q.append((i - 1, j - 1, dist + 1))
q.append((i - 1, j, dist + 1))
q.append((i - 1, j + 1, dist + 1))
q.append((i, j - 1, dist + 1))
q.append((i, j + 1, dist + 1))
q.append((i + 1, j - 1, dist + 1))
q.append((i + 1, j, dist + 1))
q.append((i + 1, j + 1, dist + 1))
return 0
m = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]
for i in guards(m):
print(i)
Iterating over the entire matrix and using BFS to find the nearest guard is the way to go. O(n^2) where n is the number of entries in the matrix.
from collections import deque
def guards(m):
d = empty_copy(m)
for i in range(0, len(m)):
for j in range(0, len(m[i])):
d[i][j] = guards_dist(m, i, j)
format(m, d)
return d
def empty_copy(m):
res = []
for i in range(0, len(m)):
res.append([])
for j in range(0, len(m[i])):
res[i].append(None)
return res
def format(m, d):
for i in range(0, len(m)):
for j in range(0, len(m[i])):
if m[i][j] == "G" or m[i][j] == "W":
d[i][j] = m[i][j]
else:
d[i][j] = str(d[i][j])
def guards_dist(m, i, j):
seen = {}
q = deque([(i, j, 0)])
while len(q) > 0:
i, j, dist = q.popleft()
if i < 0 or i >= len(m) or j < 0 or j >= len(m[i]) or (i, j) in seen:
continue
seen[(i, j)] = True
if m[i][j] == "G":
return dist
elif m[i][j] == "W":
continue
else:
q.append((i - 1, j - 1, dist + 1))
q.append((i - 1, j, dist + 1))
q.append((i - 1, j + 1, dist + 1))
q.append((i, j - 1, dist + 1))
q.append((i, j + 1, dist + 1))
q.append((i + 1, j - 1, dist + 1))
q.append((i + 1, j, dist + 1))
q.append((i + 1, j + 1, dist + 1))
return 0
m = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]
for i in guards(m):
print(i)
Space complexity: rowxcol is unavoidable as new matrix is needed. For simplicity, I am using row+2 x col+2 matrix as internal buffer. And output is generated from central part of rowxcol. In addition, I use similar size boolean matrix to track visited node.
So, space = O(rowXcol)
Time complexity: For every guard, BFS is performed. So, O(nrc) where n = number of gurads, r = rows, c = columns
struct cellNode{
pair<int, int> pos;
int depth;
};
void bfs(vector<string> & os, vector<vector<bool>> visited, int y, int x){
int rows = os.size()-2;
int cols = os[0].length()-2;
//cout << "DBG: row x col = " << rows << ", " << cols << endl;
vector<pair<int, int>> exp = {{0,-1},{0,1},{-1,0},{1,0}};
queue<cellNode> posQ;
cellNode cell;
cell.depth = 0;
cell.pos.first = y;
cell.pos.second = x;
posQ.push(cell);
visited[y][x] = true;
int i , j;
while(!posQ.empty()){
cellNode cell = posQ.front();
int y = cell.pos.first;
int x = cell.pos.second;
int d = cell.depth;
posQ.pop();
if(os[y][x]!='W' && os[y][x]!='G'){
if(os[y][x]=='O'){
os[y][x] = '0' + d;
}else{
int old = os[y][x] - '0';
if(old>d){
os[y][x] = '0' + d;
}
}
}
//cout << "DBG: current poped = " << y << ", " << x << endl;
for(int p = 0 ; p<exp.size(); ++p){
int i = exp[p].first;
int j = exp[p].second;
int posy = y+i, posx = x+j;
if(!visited[posy][posx] && os[posy][posx]!='W' && os[posy][posx]!='G' && posy!=0 && posx!=0 && posy!=(rows+1) && posx!=(cols+1)){
cellNode cell;
cell.pos.first = posy;
cell.pos.second = posx;
cell.depth = d + 1;
posQ.push(cell);
visited[posy][posx] = true;
}
}
}
}
vector<string> guardMatrix(vector<string> map){
int rows = map.size();
int cols = map[0].length();
string temp(cols+2,'W');
vector<string> os(rows+2, temp);
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
os[i+1][j+1] = map[i][j];
}
}
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
if(map[i][j]=='G'){
//cout << "DBG: gurad = " << i << ", " << j << endl;
vector<vector<bool>> visited(rows+2, vector<bool>(cols+2,false));
bfs(os, visited, i+1, j+1);
}
}
}
vector<string> result = map;
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
if(map[i][j]=='O')
result[i][j] = os[i+1][j+1];
}
}
return result;
}
int main(){
/*vector<string> map = {"WWWW",
"GOOO",
"OWWG",
"OWOO",};*/
/*vector<string> map = {"GOWWO",
"OWOOO",
"OOWWO",
"OOOOG"}; */
vector<string> map = {"OOGOW",
"OOOOO",
"OWGWO",
"OOOOO",
"GOWOO"};
vector<string> newMap = guardMatrix(map);
for(auto & s : newMap)
cout << s << endl;
}
class Solution {
class Position{
int i;
int j;
int distance;
public Position(int i, int j, int dist){
this.i = i;
this.j = j;
this.distance = dist;
}
public Position(){
this.i = -1;
this.j = -1;
this.distance = -1;
}
}
public static void main(String[] args) {
char[][] matrix = {{'o','o','o','g','o'},
{'o','o','w','o','o'},
{'o','g','o','o','w'},
{'o','w','g','o','o'},
{'w','o','o','o','g'}
};
Solution sol = new Solution();
int[][] result = sol.findDistance(matrix);
if(result == null) {
System.out.println("Invalid input Matrix");
}
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 int[][] findDistance(char[][] matrix){
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return null;
}
int[][] result = new int[matrix.length][matrix[0].length];
Queue<Position> q = new LinkedList<Position>();
// finding Guards location and adding into queue
for(int i=0; i < matrix.length; i++) {
for(int j=0; j < matrix[0].length; j++) {
if(matrix[i][j] =='g'){
q.offer(new Position(i, j, 0));
}
result[i][j] = -1;
}
}
while(!q.isEmpty()) {
Position p = q.poll();
result[p.i][p.j] = p.distance;
updateNeighbors(p, matrix, q, result);
}
return result;
}
public void updateNeighbors(Position p, char[][] matrix, Queue<Position> q, int[][] result) {
int[][] indexArray = {{-1,0},{0,1},{1,0},{0,-1}};
for(int[] index: indexArray) {
if(isValid(p.i+index[0], p.j+index[1], matrix, result)) {
result[p.i+index[0]][p.j + index[1]] = p.distance + 1;
q.offer(new Position(p.i+index[0], p.j+index[1], p.distance+1));
}
}
}
public boolean isValid(int i, int j, char[][] matrix, int[][] result) {
if((i < 0 || i > matrix.length -1) || (j < 0 || j > matrix[0].length -1) || matrix[i][j] == 'w' || result[i][j] != -1) {
return false;
}
return true;
}
}
My Solution uses branch and bound (B&B) with dynamic programming using distance travelled to estimate the closest guard. drawback is sorting
time complexity and size is 0(n^2).
package com.test;
import java.util.ArrayList;
import java.util.Collections;
public class DPMuseumMatrix {
static String SPACE = "O";
static String GUARD = "G";
static String WALL = "W";
String[][] museum;
public DPMuseumMatrix(String[][] museum) {
this.museum = museum;
}
public String[][] getDistanceMatrix() {
for (int i = 0; i < museum.length; i++)
for (int j = 0; j < museum[0].length; j++)
if (museum[i][j].equals(SPACE))
findGuard(i, j);
return museum;
}
protected void findGuard(int x, int y) {
ArrayList<Element> traveledPaths = new ArrayList<Element>();
ArrayList<Element> queue = new ArrayList<Element>();
queue.add(new Element(x, y));
Element ret = null;
while (true) {
if (isGuard(queue.get(0))) {
ret = queue.remove(0).parent;
break;
} else {
Element parent = queue.remove(0);
if (parent == null)
break;
traveledPaths.add(parent);
ArrayList<Element> children = getAdjacentChildren(traveledPaths, parent);
queue.addAll(children);
Collections.sort(queue);
}
}
if (ret != null)
updateMatrix(ret);
}
protected boolean isGuard(Element e) {
return museum[e.x][e.y].equals(GUARD);
}
protected void updateMatrix(Element path) {
int distance = 1;
while (path != null) {
if (museum[path.x][path.y] == "O")
museum[path.x][path.y] = "" + distance;
else if (isDistance(museum[path.x][path.y]))
distance = Integer.parseInt(museum[path.x][path.y]);
path = path.parent;
distance++;
}
}
protected boolean isDistance(String str) {
try{
Integer.parseInt(str);
return true;
} catch(Exception e) {
return false;
}
}
protected ArrayList<Element> getAdjacentChildren(ArrayList<Element> traveledPaths,
Element e) {
ArrayList<Element> l = new ArrayList<Element>();
if (e.y + 1 < museum[0].length && isValidChild(traveledPaths, e.x, e.y + 1))
l.add(new Element(e, e.x, e.y + 1));
if (e.x + 1 < museum.length && isValidChild(traveledPaths, e.x + 1, e.y))
l.add(new Element(e, e.x + 1, e.y));
if (e.y - 1 >= 0 && isValidChild(traveledPaths, e.x, e.y - 1))
l.add(new Element(e, e.x, e.y - 1));
if (e.x - 1 >= 0 && isValidChild(traveledPaths, e.x - 1, e.y))
l.add(new Element(e, e.x - 1, e.y));
return l;
}
protected boolean isValidChild(ArrayList<Element> traveledPaths, int x, int y) {
//check if position is in a travelled path
for (Element e : traveledPaths)
if (e.x == x && e.y == y)
return false;
//element is a wall
return !museum[x][y].equals(WALL);
}
///Linked list to handle paths to goal
public class Element implements Comparable<Element> {
int x;
int y;
Integer distanceTraveled;
Element parent;
public Element(int x, int y) {
this.x = x;
this.y = y;
distanceTraveled = 1;
}
public Element(Element parent, int x, int y) {
this(x, y);
distanceTraveled += parent.distanceTraveled;
this.parent = parent;
}
@Override
public int compareTo(Element e) {
return this.distanceTraveled.compareTo(e.distanceTraveled);
}
}
public static void main(String[] args) {
String[][] museum = {
{ "O", "O", "W", "G", "O" },
{ "O", "O", "O", "O", "W" },
{ "O", "W", "O", "O", "O" },
{ "W", "W", "O", "W", "W" },
{ "G", "W", "O", "W", "G" },
{ "O", "O", "O", "O", "O" } };
print("original", museum);
String[][] ret = new DPMuseumMatrix(museum).getDistanceMatrix();
print("result", ret);
}
public static void print(String label, String[][] museum) {
System.out.println(label);
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++)
System.out.print(museum[i][j] + " ");
System.out.println();
}
System.out.println();
}
}
def printM(m):
for row in m:
for e in row:
print('{}\t'.format(str(e)), end='')
print('')
print('')
def handle_element(element, count, replaced):
if element == 'G':
count = 0
elif element == 'W':
count = -1
elif element == 'O':
if count > -1:
count += 1
element = count
replaced = True
else: # number
if count > -1:
count += 1
if count < element:
element = count
replaced = True
if element < count:
count = element
else:
count = element
return element, count, replaced
def replace_once(m):
replaced = False
iRanges = [list(range(len(m))), list(reversed(range(len(m))))]
jRanges = [list(range(len(m[0]))), list(reversed(range(len(m[0]))))]
for i in iRanges[0]:
for jRange in jRanges: # twice
count = -1
for j in jRange:
m[i][j], count, replaced = handle_element(m[i][j], count, replaced)
for j in jRanges[0]:
for iRange in iRanges: # twice
count = -1
for i in iRange:
m[i][j], count, replaced = handle_element(m[i][j], count, replaced)
return replaced, m
def replace(m):
replaced = True
while replaced:
replaced, m = replace_once(m)
printM(m)
m = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]
printM(m)
replace(m)
Simple algorithm: on each iteration we check the nearest cells and set the current value as smallest + 1. Then just iterate until there's no updates.
from pprint import pprint
m0 = [
['W', 'W', 'O', 'W', 'G'],
['W', 'W', 'O', 'O', 'O'],
['O', 'O', 'O', 'W', 'O'],
['O', 'W', 'W', 'W', 'O'],
['O', 'O', 'O', 'W', 'O'],
]
m1 = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]
m2 = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]
def calculate_museum(museum):
size = len(museum)
updates = 0
for x in xrange(size):
for y in xrange(size):
res = None
if museum[x][y] is 'O':
if x > 0:
res = test_cell(museum[x-1][y], museum[x][y])
if res:
museum[x][y] = res
updates += 1
if x < (size-1):
res = test_cell(museum[x+1][y], museum[x][y])
if res:
museum[x][y] = res
updates += 1
if y > 0:
res = test_cell(museum[x][y-1], museum[x][y])
if res:
museum[x][y] = res
updates += 1
if y < (size-1):
res = test_cell(museum[x][y+1], museum[x][y])
if res:
museum[x][y] = res
updates += 1
if updates > 0:
calculate_museum(museum)
def test_cell(cell, cur):
if cell is 'G':
return 1
if isinstance(cell, int):
if cur and cell > cur:
return None
return cell+1
return None
pprint(m0)
calculate_museum(m0)
print("Result:")
pprint(m0)
print
pprint(m1)
calculate_museum(m1)
print("Result:")
pprint(m1)
print
pprint(m2)
calculate_museum(m2)
print("Result:")
pprint(m2)
#include <vector>
#include <list>
#include <iostream>
using namespace std;
enum {W = -2, G = -1, O = 0};
struct OpenSpace {
int x;
int y;
int distance;
};
void findGuard (const vector<vector<int>> & matrix, list<pair<int, int>> & guards) {
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
if (matrix[i][j] == G) {
guards.push_back({i, j});
}
}
}
}
void inspect(vector<vector<int>> & matrix, list<OpenSpace> & queue) {
int curX = queue.front().x, curY = queue.front().y;
int distance = queue.front().distance;
queue.pop_front();
int shift[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
for(int i = 0; i < 4; i++) {
int x = curX + shift[i][0];
int y = curY + shift[i][1];
if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()
&& matrix[x][y] != G && matrix[x][y] != W) {
if (matrix[x][y] == O || matrix[x][y] > distance + 1) {
matrix[x][y] = distance + 1;
queue.emplace_back(OpenSpace({x, y, distance+1}));
}
}
}
}
void findCoverage(vector<vector<int>> & matrix) {
list<pair<int, int>> guards;
findGuard(matrix, guards);
for (pair<int, int> xy : guards) {
list<OpenSpace> queue;
queue.emplace_back(OpenSpace({xy.first, xy.second, 0}));
// do BFS for each guard
while (!queue.empty()) {
inspect(matrix, queue);
}
}
}
int main() {
vector<vector<int>> matrix =
{{O, W, O, G, O},
{G, G, W, O, O},
{W, O, O, W, O},
{O, O, G, O, G}};
findCoverage(matrix);
for (auto row : matrix) {
for (auto i : row) {
printf("%2d ", i);
}
printf("\n");
}
}
A solution based on graph and breadth-first traverse is present here: cpluspluslearning-petert.blogspot.co.uk/2016/06/data-structure-and-algorithm-find.html
Test code
void TestGetDistances()
{
{
const std::vector<std::vector<MuseumItem>> museum =
{{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN} };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0))->second == 4);
assert(distances.find(std::make_tuple(1, 0))->second == 3);
assert(distances.find(std::make_tuple(2, 0))->second == 2);
assert(distances.find(std::make_tuple(3, 0))->second == 3);
assert(distances.find(std::make_tuple(4, 0))->second == 4);
assert(distances.find(std::make_tuple(0, 1))->second == 3);
assert(distances.find(std::make_tuple(1, 1))->second == 2);
assert(distances.find(std::make_tuple(2, 1))->second == 1);
assert(distances.find(std::make_tuple(3, 1))->second == 2);
assert(distances.find(std::make_tuple(4, 1))->second == 3);
assert(distances.find(std::make_tuple(0, 2))->second == 2);
assert(distances.find(std::make_tuple(1, 2))->second == 1);
assert(distances.find(std::make_tuple(2, 2)) == distances.end());
assert(distances.find(std::make_tuple(3, 2))->second == 1);
assert(distances.find(std::make_tuple(4, 2))->second == 2);
assert(distances.find(std::make_tuple(0, 3))->second == 3);
assert(distances.find(std::make_tuple(1, 3))->second == 2);
assert(distances.find(std::make_tuple(2, 3))->second == 1);
assert(distances.find(std::make_tuple(3, 3))->second == 2);
assert(distances.find(std::make_tuple(4, 3))->second == 3);
assert(distances.find(std::make_tuple(0, 4))->second == 4);
assert(distances.find(std::make_tuple(1, 4))->second == 3);
assert(distances.find(std::make_tuple(2, 4))->second == 2);
assert(distances.find(std::make_tuple(3, 4))->second == 3);
assert(distances.find(std::make_tuple(4, 4))->second == 4);
}
{
const std::vector<std::vector<MuseumItem>> museum =
{ { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN } };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0)) == distances.end());
assert(distances.find(std::make_tuple(1, 0)) == distances.end());
assert(distances.find(std::make_tuple(2, 0)) == distances.end());
assert(distances.find(std::make_tuple(3, 0)) == distances.end());
assert(distances.find(std::make_tuple(4, 0)) == distances.end());
assert(distances.find(std::make_tuple(0, 1)) == distances.end());
assert(distances.find(std::make_tuple(1, 1)) == distances.end());
assert(distances.find(std::make_tuple(2, 1)) == distances.end());
assert(distances.find(std::make_tuple(3, 1)) == distances.end());
assert(distances.find(std::make_tuple(4, 1)) == distances.end());
assert(distances.find(std::make_tuple(0, 2))->second == 2);
assert(distances.find(std::make_tuple(1, 2))->second == 1);
assert(distances.find(std::make_tuple(2, 2)) == distances.end());
assert(distances.find(std::make_tuple(3, 2))->second == 1);
assert(distances.find(std::make_tuple(4, 2))->second == 2);
assert(distances.find(std::make_tuple(0, 3))->second == 3);
assert(distances.find(std::make_tuple(1, 3))->second == 2);
assert(distances.find(std::make_tuple(2, 3))->second == 1);
assert(distances.find(std::make_tuple(3, 3))->second == 2);
assert(distances.find(std::make_tuple(4, 3))->second == 3);
assert(distances.find(std::make_tuple(0, 4))->second == 4);
assert(distances.find(std::make_tuple(1, 4))->second == 3);
assert(distances.find(std::make_tuple(2, 4))->second == 2);
assert(distances.find(std::make_tuple(3, 4))->second == 3);
assert(distances.find(std::make_tuple(4, 4))->second == 4);
}
{
const std::vector<std::vector<MuseumItem>> museum =
{ { MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN },
{ MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN } };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0)) == distances.end());
assert(distances.find(std::make_tuple(1, 0))->second == 1);
assert(distances.find(std::make_tuple(2, 0))->second == 1);
assert(distances.find(std::make_tuple(3, 0)) == distances.end());
assert(distances.find(std::make_tuple(4, 0))->second == 1);
assert(distances.find(std::make_tuple(0, 1))->second == 1);
assert(distances.find(std::make_tuple(1, 1))->second == 2);
assert(distances.find(std::make_tuple(2, 1))->second == 2);
assert(distances.find(std::make_tuple(3, 1))->second == 1);
assert(distances.find(std::make_tuple(4, 1))->second == 2);
assert(distances.find(std::make_tuple(0, 2)) == distances.end());
assert(distances.find(std::make_tuple(1, 2)) == distances.end());
assert(distances.find(std::make_tuple(2, 2))->second == 1);
assert(distances.find(std::make_tuple(3, 2)) == distances.end());
assert(distances.find(std::make_tuple(4, 2)) == distances.end());
assert(distances.find(std::make_tuple(0, 3))->second == 2);
assert(distances.find(std::make_tuple(1, 3))->second == 1);
assert(distances.find(std::make_tuple(2, 3)) == distances.end());
assert(distances.find(std::make_tuple(3, 3))->second == 1);
assert(distances.find(std::make_tuple(4, 3))->second == 2);
assert(distances.find(std::make_tuple(0, 4))->second == 3);
assert(distances.find(std::make_tuple(1, 4))->second == 2);
assert(distances.find(std::make_tuple(2, 4))->second == 1);
assert(distances.find(std::make_tuple(3, 4))->second == 2);
assert(distances.find(std::make_tuple(4, 4))->second == 3);
}
}
I also iterate over each guard (as I find them using a generator).
For each guard I do a BFS and update any distances in place.
It won't update distances if it is a wall or there's a shorter distance at that location already (near another guard).
A little optimisation that, depending on the configuration of the board, might save some time on average is:
Don't explore neighbours of locations that already have a shorter distance to another guard. Because of the BFS expansion, it means it isn't possible to find another location with a shorter distance afterwards. (p.s. that's an advantage over doing DFS here).
Here's my Python solution:
class GuardDistance(object):
def __init__(self, matrix):
self._matrix = matrix
self._size = len(matrix)
def matrix(self):
return self._matrix
def calculate_distances(self):
for gx, gy in self._find_guards():
visited = set()
frontier = self._neighbours(gx, gy, 0, visited)
while frontier:
(x, y), distance = frontier.pop(0)
visited.add((x, y))
if self._update(x, y, distance):
frontier += self._neighbours(x, y, distance, visited)
def _find_guards(self):
return ((x, y) for x in xrange(self._size)
for y in xrange(self._size)
if self._matrix[x][y] == 'G')
def _neighbours(self, x, y, distance, visited):
neighbours = []
for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nx, ny = x + dx, y + dy
if self._valid_location(nx, ny) and (nx, ny) not in visited:
neighbours.append(((nx, ny), distance + 1))
return neighbours
def _valid_location(self, x, y):
return 0 <= x < self._size and 0 <= y < self._size
def _update(self, x, y, distance):
value = self._matrix[x][y]
if str(value) not in 'GW' and (value == 'O' or value >= distance):
self._matrix[x][y] = distance
return True
else:
return False
# ere's some code to run this
solution = GuardDistance([['O','O','O','G'],
['O','W','W','W'],
['O','W','G','W'],
['O','O','O','O']])
solution.calculate_distances()
print solution.matrix()
Iterate over each guard and BFS. For every new BFS level the total distance increase by one, don't include neighbors that are walls or have lesser value than the current distance.
Diagonal moves are valid.
import collections
def initialize(m, dest, q):
value_map = {'g': 0, 'o': float('inf'), 'w': -1}
for i in range(len(m)):
dest.append([0] * len(m[0]))
for j in range(len(m[0])):
dest[i][j] = value_map[m[i][j].lower()]
if m[i][j].lower() == 'g':
q.append((i, j))
def guard_distance(m):
result = []
q = collections.deque()
# Valid moves are all directions (diagonals included)
surroundings = [(-1, -1), (-1, 0), (-1, +1), (0, -1),
(0, +1), (+1, 0), (+1, -1), (+1, +1)]
initialize(m, result, q)
dist = 1
while q:
# Empty first level before increasing
# distance
for _ in range(len(q)):
curr = q.popleft()
for coord in surroundings:
i = curr[0] + coord[0]
j = curr[1] + coord[1]
try:
if result[i][j] > dist:
result[i][j] = dist
q.append((i, j))
except IndexError:
# Hit matrix borders
pass
dist += 1
return result
m = [['g', 'w', 'o', 'o', 'w'],
['o', 'w', 'o', 'W', 'w'],
['o', 'o', 'o', 'o', 'w'],
['O', 'w', 'o', 'G', 'w'],
['G', 'w', 'w', 'o', 'w']]
print '\n'.join(str(x) for x in guard_distance(m))
Lengthy but should do the work. A lot of hard coding but you get the point.
char m2[5][5] = {
{'O', 'O', 'G', 'G', 'G'},
{'O', 'W', 'O', 'O', 'O'},
{'O', 'W', 'G', 'W', 'O'},
{'O', 'W', 'W', 'W', 'O'},
{'O', 'O', 'O', 'O', 'O'}};
int dist[5][5] = {
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0}};
int least_min_nearby_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (dist[i][j]>0){
return dist[i][j]+1;
}
return 1000;
}
return 1000;
}
int least_min_nearby(int i, int j, int iter){
int left = 0, right =0, top=0, bottom=0, min_i=0,min_j=0,min=0;
//printf("i=%d,j=%d\n",i,j);
left = least_min_nearby_i_j(i-1,j);
right = least_min_nearby_i_j(i+1,j);
top = least_min_nearby_i_j(i,j-1);
bottom = least_min_nearby_i_j(i,j+1);
min_i = (left < right) ? left : right;
min_j = (top < bottom) ? top : bottom;
min = (min_i < min_j) ? min_i : min_j;
if (min > iter){
return 0;
}
return min;
}
int check_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (m2[i][j] == 'G'){
return 1;
}
}
return 0;
}
int check_nearby(int i,int j){
int left = 0, right =0, top=0, bottom=0;
//printf("i=%d,j=%d\n",i,j);
left = check_i_j(i-1,j);
right = check_i_j(i+1,j);
top = check_i_j(i,j-1);
bottom = check_i_j(i,j+1);
//printf("%d%d%d%d\n",top,left,right,bottom);
if (left || right || top || bottom)
return 1;
return 0;
}
int main(void) {
// your code goes here
int i=0,j=0,count=0,iter=0;
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
switch (m2[i][j])
{
case 'G': dist[i][j] = -1;
break;
case 'W': dist[i][j] = -2;
break;
case 'O': dist[i][j] = check_nearby(i,j);
break;
}
if (dist[i][j] == 0){
count++;
}
}
}
iter=1;
while (count > 0){
iter++;
count = 0;
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (dist[i][j] == 0){
dist[i][j] = least_min_nearby(i,j,iter);
}
if (dist[i][j] == 0){
count++;
}
}
}
}
for (i=0;i<5;i++){
for (j=0;j<5;j++)
printf("%02d ", dist[i][j]);
printf("\n");
}
return 0;
}
char m2[5][5] = {
{'O', 'O', 'G', 'G', 'G'},
{'O', 'W', 'O', 'O', 'O'},
{'O', 'W', 'G', 'W', 'O'},
{'O', 'W', 'W', 'W', 'O'},
{'O', 'O', 'O', 'O', 'O'}};
int dist[5][5] = {
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0}};
int least_min_nearby_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (dist[i][j]>0){
return dist[i][j]+1;
}
return 1000;
}
return 1000;
}
int least_min_nearby(int i, int j, int iter){
int left = 0, right =0, top=0, bottom=0, min_i=0,min_j=0,min=0;
//printf("i=%d,j=%d\n",i,j);
left = least_min_nearby_i_j(i-1,j);
right = least_min_nearby_i_j(i+1,j);
top = least_min_nearby_i_j(i,j-1);
bottom = least_min_nearby_i_j(i,j+1);
min_i = (left < right) ? left : right;
min_j = (top < bottom) ? top : bottom;
min = (min_i < min_j) ? min_i : min_j;
if (min > iter){
return 0;
}
return min;
}
int check_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (m2[i][j] == 'G'){
return 1;
}
}
return 0;
}
int check_nearby(int i,int j){
int left = 0, right =0, top=0, bottom=0;
//printf("i=%d,j=%d\n",i,j);
left = check_i_j(i-1,j);
right = check_i_j(i+1,j);
top = check_i_j(i,j-1);
bottom = check_i_j(i,j+1);
//printf("%d%d%d%d\n",top,left,right,bottom);
if (left || right || top || bottom)
return 1;
return 0;
}
int main(void) {
// your code goes here
int i=0,j=0,count=0,iter=0;
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
switch (m2[i][j])
{
case 'G': dist[i][j] = -1;
break;
case 'W': dist[i][j] = -2;
break;
case 'O': dist[i][j] = check_nearby(i,j);
break;
}
if (dist[i][j] == 0){
count++;
}
}
}
iter=1;
while (count > 0){
iter++;
count = 0;
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (dist[i][j] == 0){
dist[i][j] = least_min_nearby(i,j,iter);
}
if (dist[i][j] == 0){
count++;
}
}
}
}
for (i=0;i<5;i++){
for (j=0;j<5;j++)
printf("%02d ", dist[i][j]);
printf("\n");
}
return 0;
}
def replace_with_distance(M, guard_x, guard_y, shortest):
if not guard_x >= len(M) and not guard_y >= len(M) \
and not guard_x < 0 and not guard_y < 0 \
and M[guard_x][guard_y] != 'W':
if M[guard_x][guard_y] == 'G':
M[guard_x][guard_y] = 0
replace_with_distance(M, guard_x + 1, guard_y, 0)
replace_with_distance(M, guard_x, guard_y + 1, 0)
replace_with_distance(M, guard_x - 1, guard_y, 0)
replace_with_distance(M, guard_x, guard_y - 1, 0)
elif M[guard_x][guard_y] == 'O' or M[guard_x][guard_y] > shortest + 1:
M[guard_x][guard_y] = shortest + 1
replace_with_distance(M, guard_x + 1, guard_y, shortest + 1)
replace_with_distance(M, guard_x, guard_y + 1, shortest + 1)
replace_with_distance(M, guard_x - 1, guard_y, shortest + 1)
replace_with_distance(M, guard_x, guard_y - 1, shortest + 1)
My method requires to traverse through the matrix, update the steps as long as it is an open space by (1) look through surrounding neighbors for guards (2) looks for open space with steps updated and simply add them up (3) look for open space and move towards there, therefore incrementing the steps. Time complexity is O(n^2).
public static void main(String args[]) {
char[][] arr = {{'O', 'O', 'O', 'G'}, {'W', 'G', 'O', 'O'}, {'O', 'O', 'W', 'G'}, {'W', 'O', 'O', 'O'}};
arr = updateMatrix(arr);
for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr[i].length; j++) {
if (j==0)
System.out.print(arr[i][j]);
else
System.out.print(" "+arr[i][j]);
}
System.out.print("\n");
}
}
private static char[][] updateMatrix (char arr[][]){
for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr[i].length; j++) {
if (arr[i][j] == 'O') {
int step = 1;
step += lookSurrounding(arr, i, j, arr.length);
//to convert to int - RADIX = 10
arr[i][j] = Character.forDigit(step, 10);
}
}
}
return arr;
}
private static int lookSurrounding(char arr[][],
int row,
int col,
int arraySize) {
//represent Up, Down, Left, Right
Character[] surroundingVal = {'E', 'E', 'E', 'E'};
int existingStep = -1;
//up
if (row - 1 >= 0) {
surroundingVal[0] = arr[row-1][col];
existingStep = Character.isDigit(surroundingVal[0]) && Character.getNumericValue(surroundingVal[0]) > existingStep
? Character.getNumericValue(surroundingVal[0]) : existingStep;
}
//down
if (row + 1 < arraySize) {
surroundingVal[1] = arr[row + 1][col];
existingStep = Character.isDigit(surroundingVal[1]) && Character.getNumericValue(surroundingVal[1]) > existingStep
? Character.getNumericValue(surroundingVal[1]) : existingStep;
}
//left
if (col - 1 >= 0) {
surroundingVal[2] = arr[row][col - 1];
existingStep = Character.isDigit(surroundingVal[2]) && Character.getNumericValue(surroundingVal[2]) > existingStep
? Character.getNumericValue(surroundingVal[2]) : existingStep;
}
//right
if (col + 1 < arraySize) {
surroundingVal[3] = arr[row][col+1];
existingStep = Character.isDigit(surroundingVal[3]) && Character.getNumericValue(surroundingVal[3]) > existingStep
? Character.getNumericValue(surroundingVal[3]) : existingStep;
}
if (Arrays.asList(surroundingVal).contains('G'))
return 0;
else if (existingStep > -1 )
return existingStep;
else if (Arrays.asList(surroundingVal).contains('O')) {
int step = 1;
int index = Arrays.asList(surroundingVal).indexOf('O');
int newRow = row, newCol = col;
if (index == 0)
newRow = row - 1;
else if (index == 1)
newRow = row + 1;
else if (index == 2)
newCol = col - 1;
else if (index == 3)
newCol = col + 1;
step += lookSurrounding(arr, newRow, newCol, arraySize);
return step;
}
//cater for error
return 0;
}
BFS solution starting at the guards. O(n^2) time and space:
class Square{
int x, y, distance;
Square(int x, int y, int distance){
this.x = x;
this.y = y;
this.distance = distance;
}
}
static int[][] DIRECTIONS = new int[]{{0, 1}, {0, -1}, {1, 0}, {-1,0}};
public int[][] getDistances(char[][] museum){
int n = museum.length;
int m = museum[0].length;
if(n == 0 || m == 0)
return null;
boolean[][] visited = new boolean[n][m];
int[][] result = new int[n][m];
Queue<Square> squares = new Queue<Square>();
//BFS starting at the guards
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(museum[i][j] == ‘G’){
squares.add(new Square(i, j, 0));
visited[i][j] = true;
}else{
if(museum[i][j] == ‘W’){
visited[i][j] = true;
}
//By default no way to reach a guard
result[i][j] = -1;
}
}
}
while(!squares.isEmpty()){
Square square = squares.pop();
result[square.x][square.y] = square.distance;
for(int[] direction : directions]){
int x = square.x + direction[0];
int y = square.y + direction[1];
if(x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]){
squares.add(new Square(x, y, square.distance + 1);
visited[x][y] = true;
}
}
}
}
My solution is by doing a BFS and then adjust the steps away from the "G" when popping the stack.
public class Quiz_OpenSpaceInMuseum {
public static void main(String args[]) {
// O O O
// O W W
// G O G
//
// to
//
// 2 3 4
// 1 W W
// G 1 G
String[][] input = new String[][]{
{"O", "O", "O"},
{"O", "W", "W"},
{"G", "O", "G"}};
String[][] output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));
// O O O O
// O W O G
// O W O O
// O G O O
//
// to
//
// 4 3 2 1
// 3 W 1 G
// 2 W 2 1
// 1 G 1 2
input = new String[][]{
{"O", "O", "O", "O"},
{"O", "W", "O", "G"},
{"O", "W", "O", "O"},
{"O", "G", "O", "O"}};
output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));
// O W G O
// O W W O
// O W O O
// O O O G
//
// to
//
// 6 W G 1
// 5 W W 2
// 4 W 2 1
// 3 2 1 G
input = new String[][]{
{"O", "W", "G", "O"},
{"O", "W", "W", "O"},
{"O", "W", "O", "O"},
{"O", "O", "O", "G"}};
output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));
// O O G G G
// O W O O O
// O W G W O
// O W W W O
// O O O O O
//
// to
//
// 2 1 G G G
// 3 W 1 1 1
// 4 W G W 2
// 5 W W W 3
// 6 7 6 5 4
input = new String[][]{
{"O", "O", "G", "G", "G"},
{"O", "W", "O", "O", "O"},
{"O", "W", "G", "W", "O"},
{"O", "W", "W", "W", "O"},
{"O", "O", "O", "O", "O"}};
output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));
}
///////////////////////////////////////////////////////////////////////////
// Protected / Private Methods ////////////////////////////////////////////
private int mIterationCount = 0;
private static final String OPEN = String.valueOf("O");
private static final String GUARD = String.valueOf("G");
private String[][] findOpenSpaceByBrutalForce(String[][] museum) {
String[][] clone = new String[museum.length][museum.length];
List<Position> guardPosList = new ArrayList<>();
// DEBUG: Init the iteration counter.
mIterationCount = 0;
// Clone the space and find the "G".
// Complexity: O(n^2).
for (int y = 0; y < museum.length; ++y) {
for (int x = 0; x < museum.length; ++x) {
// DEBUG: Accumulate the iteration counter.
++mIterationCount;
clone[y][x] = museum[y][x];
if (museum[y][x].equals(GUARD)) {
guardPosList.add(new Position(x, y));
}
}
}
// Search from a "G" to another "G".
// Complexity: maximum O(n^2)
for (Position pos : guardPosList) {
// Where the guard is at.
findGuard(clone,
pos.x,
pos.y,
0);
}
return clone;
}
private int findGuard(String[][] museum,
int x,
int y,
int step) {
// Scan if the guard is adjacent. If so, stop the searching.
int right = x + 1 < museum.length ? x + 1 : x;
int left = x - 1 >= 0 ? x - 1 : x;
int bottom = y + 1 < museum.length ? y + 1 : y;
int top = y - 1 >= 0 ? y - 1 : y;
if ((right != x && // right.
museum[y][x + 1].equals(GUARD)) ||
(bottom != y && // bottom.
museum[y + 1][x].equals(GUARD)) ||
(left != x && // left.
museum[y][x - 1].equals(GUARD)) ||
(top != y && // top.
museum[y - 1][x].equals(GUARD))) {
// There is a GUARD around, correct the suggested step away from
// the GUARD.
step = 1;
}
if (!museum[y][x].equals(GUARD)) {
museum[y][x] = Integer.toString(step);
}
Stack<Position> todo = new Stack<>();
// Try right one.
if (right != x &&
museum[y][right].equals(OPEN)) {
todo.push(new Position(right, y));
}
// Try bottom one.
if (bottom != y &&
museum[bottom][x].equals(OPEN)) {
todo.push(new Position(x, bottom));
}
// Try left one.
if (left != x &&
museum[y][left].equals(OPEN)) {
todo.push(new Position(left, y));
}
// Try top one.
if (top != y &&
museum[top][x].equals(OPEN)) {
todo.push(new Position(x, top));
}
while (!todo.isEmpty()) {
Position next = todo.pop();
// Compare the returned step with current step.
// If the returned step is less than the current step, it means
// that there is a shorter path and the current step should be
// adjusted.
int stepAwayFromGuard = findGuard(museum, next.x, next.y, step + 1);
if (step > stepAwayFromGuard) {
museum[y][x] = Integer.toString(stepAwayFromGuard);
step = stepAwayFromGuard;
}
}
// DEBUG: Accumulate the iteration counter.
++mIterationCount;
return step + 1;
}
private void print(String[][] space) {
for (int y = 0; y < space.length; ++y) {
for (int x = 0; x < space.length; ++x) {
System.out.print(space[y][x]);
if (x < space.length - 1) {
System.out.print(" ");
}
}
System.out.println();
}
}
///////////////////////////////////////////////////////////////////////////
// Clazz //////////////////////////////////////////////////////////////////
private static class Position {
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Position position = (Position) o;
if (x != position.x) return false;
return y == position.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
}
Another Java implementation for the record... BFS...
public class MuseumProblem {
static class Node {
int x;
int y;
int distance;
public Node(int x, int y, int distance) {
this.x = x;
this.y = y;
this.distance = distance;
}
public String toString() {
return "["+x+","+y+"]("+distance+")";
}
}
static void calcDistance(int r[][], Node node) {
// double check but needed...
if(node.x < 0 || node.y < 0 || node.x >= r.length || node.y >= r[0].length)
return;
int val = r[node.x][node.y];
if(val == -2) {
// System.out.println("hit a WALL");
return;
}
if(val == 0) {
// System.out.println("hit a Guard");
return;
}
if(val > 0) {
// System.out.println("already done: "+node);
return;
}
r[node.x][node.y] = node.distance+1;
}
static int[][] calculateDistance(char matrix[][]) {
int r[][] = new int[matrix.length][matrix[0].length];
Queue<Node> queue = new LinkedList<Node>();
// find Guard and sets the result matrix
// -2: to walls
// -1: to unvisited open space
// 0: to guard
// > 0: distance to Guard
for(int i=0; i < matrix.length; i++) {
for(int j=0; j < matrix[0].length; j++) {
if(matrix[i][j] == 'G') {
r[i][j] = 0;
// distance is -1 to Guard so don't need to check for Guard to +1 to distance...
// Makes the calc simply
queue.add(new Node(i,j,-1));
}
else if(matrix[i][j] == 'W')
r[i][j] = -2;
else
r[i][j] = -1;
}
}
while(!queue.isEmpty()) {
Node node = queue.poll();
calcDistance(r, node);
// calc adjacent verticies
// DOWN
int distance = node.distance + 1;
if(node.x+1 < r.length && r[node.x+1][node.y] == -1)
queue.add(new Node(node.x+1, node.y, distance));
// DOWN LEFT
if(node.x+1 < r.length && node.y-1 >= 0 && r[node.x+1][node.y-1] == -1)
queue.add(new Node(node.x+1,node.y-1, distance));
// DOWN RIGHT
if(node.x+1 < r.length && node.y+1 < r[0].length && r[node.x+1][node.y+1] == -1)
queue.add(new Node(node.x+1, node.y+1, distance));
// UP
if((node.x-1) >= 0 && r[node.x-1][node.y] == -1)
queue.add(new Node(node.x-1, node.y, distance));
// UP LEFT
if(node.x-1 >= 0 && node.y-1 >= 0 && r[node.x-1][node.y-1] == -1)
queue.add(new Node(node.x-1,node.y-1, distance));
// UP RIGHT
if(node.x-1 >= 0 && node.y+1 < r[0].length && r[node.x-1][node.y+1] == -1)
queue.add(new Node(node.x-1, node.y+1, distance));
// LEFT
if((node.y-1) >= 0 && r[node.x][node.y-1] == -1)
queue.add(new Node(node.x, node.y-1, distance));
// RIGHT
if((node.y+1) < r[0].length && r[node.x][node.y+1] == -1)
queue.add(new Node(node.x, node.y+1, distance));
}
return r;
}
public static void main(String args[]) {
char[][] matrix = {
{'G','O','O','O','O','O','O','O','O'},
{'W','W','W','W','W','W','W','W','O'},
{'O','O','O','O','O','O','O','O','O'},
{'W','W','W','W','W','O','W','W','W'},
{'O','O','O','O','O','O','O','O','O'},
{'O','W','W','W','W','W','W','W','W'},
{'G','W','O','O','O','O','O','O','O'},
{'O','O','O','W','W','W','W','W','W'}
};
int result[][] = calculateDistance(matrix);
for(int i=0; i < result.length; i++) {
for(int j=0; j < result[0].length; j++) {
if(result[i][j] == -2)
System.out.print("[WW]");
else if(result[i][j]== -1)
System.out.print("[OO]");
else if(result[i][j] == 0) {
System.out.print("[GG]");
}
else
System.out.print(String.format("[%02d]", result[i][j]));
}
System.out.println("");
}
System.out.println("");
}
}
Calculate distance from each of the 'g' to each of the 'o' (avoiding 'w' and 'g') and store the minimum distance in the result matrix. Update result matrix point if new distance is lower than stored one. Result matrix is initialised with Integer.MAX_VALUE
Below is the working code:
import java.util.*;
class Main {
static char[][] matrix = { { 'o', 'o', 'o', 'g', 'o' }, { 'o', 'o', 'w', 'o', 'o' }, { 'o', 'g', 'o', 'o', 'w' },
{ 'o', 'w', 'g', 'o', 'o' }, { 'w', 'o', 'o', 'o', 'g' } };
static int[][] result = new int[matrix.length][matrix.length];
public static void main(String[] args) {
for(int i=0;i< matrix.length;i++){
Arrays.fill(result[i],Integer.MAX_VALUE);
}
for(int i=0;i< matrix.length;i++){
for(int j=0;j< matrix.length;j++){
if(matrix[i][j]=='g'){
//calc distances
calcdistances(i,j,0);
}
}
}
//to replace Integer.MAX_VALUE with 'g' and 'w'
String[][] display = new String[matrix.length][matrix.length];
for(int i=0;i< matrix.length;i++){
for(int j=0;j< matrix.length;j++){
if(matrix[i][j]=='g'){
display[i][j]="g";
}else if(matrix[i][j]=='w'){
display[i][j]="w";
}else{
display[i][j]=result[i][j]+"";
}
}
}
for(int i=0;i< display.length;i++){
System.out.println(Arrays.toString(display[i]));
}
}
public static void calcdistances(int r, int c, int currDist){
int cleft = c-1;
if(cleft>=0 && matrix[r][cleft]!='w'&& matrix[r][cleft]!='g') {
if(result[r][cleft]>(currDist+1)){
result[r][cleft] = currDist+1;
calcdistances(r,cleft,result[r][cleft]);
}
}
int cright = c+1;
if(cright<result.length && matrix[r][cright]!='w'&& matrix[r][cright]!='g' ){
if(result[r][cright]>(currDist+1)){
result[r][cright] = currDist+1;
calcdistances(r,cright,result[r][cright]);
}
}
int rtop = r-1;
if(rtop>=0 && matrix[rtop][c]!='w'&& matrix[rtop][c]!='g') {
if(result[rtop][c]>(currDist+1)){
result[rtop][c] = currDist+1;
calcdistances(rtop,c,result[rtop][c]);
}
}
int rbottom = r+1;
if(rbottom<result.length && matrix[rbottom][c]!='w'&& matrix[rbottom][c]!='g') {
if(result[rbottom][c]>(currDist+1)){
result[rbottom][c] = currDist+1;
calcdistances(rbottom,c,result[rbottom][c]);
}
}
}
}
Output:
[3, 2, 1, g, 1]
[2, 1, w, 1, 2]
[1, g, 1, 2, w]
[2, w, g, 1, 1]
[w, 2, 1, 1, g]
My solution: First find all guards which will take O(m*n), add it to queue as you find it.
Do BFS on the elements in queue. Total time complexity will be O(m*n). Also, I am using extra result array of size m*n, so space complexity will be O(m*n). m: no of rows and n: number of columns
- sandeep1001 May 23, 2016