# Manhattan/Tchebyshev Distance - O(n^3) Solution

This is a variant of the Manhattan Distance problem. The input is a 2D matrix of boolean with the true cells representing location of an ATMs(or anything for that matter). The output has to be a 2D int matrix giving the distance of each cell from the location of the closest ATMS.

Here's my code,

public class ManhattanDistance {

public static void main(String[] args) {

boolean[][] check = new boolean;
check = new boolean[]{false, false, false, false, false};
check = new boolean[]{false, false, true, false, false};
check = new boolean[]{false, false, false, false, false};
check = new boolean[]{true, false, true, false, false};
check = new boolean[]{false, false, false, false, true};

printArray(check);
int[][] grid = manhattanDistance(check);
System.out.println("____________________________________");
printArray(grid);
}

public static int[][] manhattanDistance(boolean[][] checkList){
int[][] grid = new int[checkList.length][checkList.length];
for (int i = 0; i <grid.length ; i++) {
for (int j = 0; j < grid[i].length ; j++) {
grid[i][j] = Integer.MAX_VALUE;

}
}

for (int i = 0; i <checkList.length ; i++) {
for (int j = 0; j < checkList[i].length; j++) {
if(checkList[i][j]) spiral(i, j, grid);
}
}

for (int i = 0; i <grid.length ; i++) {
for (int j = 0; j <grid[i].length ; j++) {
if(checkList[i][j]) grid[i][j] = 0;
}
}
return grid;
}

public static void spiral(int row, int col, int[][] grid){

boolean[] conditionChecker = new boolean;
int rowMax = grid.length;
int colMax = grid.length;

while(true){
int level = 0;
//up
if(!conditionChecker) {
while(row -1 >= 0){
grid[row-1][col] = Math.min(grid[row-1][col], level+1);

level++;
row--;
}
row += level;
level = 0;
conditionChecker = true;
}

//down
if (!conditionChecker){
while(row + 1 < rowMax){
grid[row +1][col] = Math.min(grid[row+1][col], level+1);

level++;
row++;
}
row -= level;
level =0;
conditionChecker = true;
}

//right
if(!conditionChecker){
while(col + 1 < colMax){
grid[row][col +1] = Math.min(grid[row][col+1], level+1);
level++;
col++;
}
col -= level;
level = 0;
conditionChecker = true;
}

//left
if (!conditionChecker){
while(col -1 >= 0){
grid[row][col -1] = Math.min(grid[row][col-1], level+1);
level++;
col--;
}
col+= level;
level = 0;
conditionChecker = true;
}

//NE
if(!conditionChecker) {
while(row -1 >= 0 && col +1 < colMax){
grid[row-1][col+1] = Math.min(grid[row-1][col+1], level+1);
row--;
col++;
level++;
}
row+= level;
col-= level;
level = 0;
conditionChecker = true;
}

//SE
if(!conditionChecker){
while(row +1 < rowMax && col +1 < colMax){
grid[row+1][col+1] = Math.min(grid[row+1][col+1], level+1);
row++;
col++;
level++;
}
row -= level;
col -= level;
level = 0;
conditionChecker = true;
}

//NW
if(!conditionChecker){
while(row +1 < rowMax && col -1 >= 0){
grid[row+1][col-1] = Math.min(grid[row+1][col-1], level + 1);
level++;
row++;
col--;
}
row-= level;
col += level;
level = 0;
conditionChecker = true;
}

//SW
if(!conditionChecker){
if(row -1 >= 0 && col -1 >= 0){
grid[row-1][col-1] = Math.min(grid[row-1][col-1], level+1);
row--;
col--;
level++;
}
row += level;
col += level;
level = 0;
conditionChecker = true;
}

if(conditionChecker) break;
}
}

public static void printArray(int[][] arr){
for (int i = 0; i < arr.length ; i++) {
for (int j = 0; j <arr.length ; j++) {
System.out.print(arr[i][j] +" ");
}
System.out.println();
}
}
public static void printArray(boolean[][] arr){
for (int i = 0; i < arr.length ; i++) {
for (int j = 0; j <arr.length ; j++) {
if(!arr[i][j])System.out.print(0 +" ");
else System.out.print(1+ " ");
}
System.out.println();
}
}
}


The core algorithm is as follows.

1. Initialize an integer matrix with a very large number for all cells.
2. Traverse the boolean matrix
3. For every cell with an ATM spin up a search in all 8 cardinal directions level by level.
4. For every level of search the existing number is over written by a smaller number should a smaller level exist.

Invite comments and suggestions for betterment.

• Under the usual definition of Manhattan distance, there are only four directions, because you cannot travel diagonally. The distance from (0, 0) to (1, 1) is 2. – phoog May 16 '16 at 19:07
• Yup that's why I've mentioned 'a variant.' – Antithesis May 16 '16 at 19:09
• Is this Chebyshev distance? – Justin May 16 '16 at 19:15
• Infact I wasn't aware of this, but looks like this is Tchebyshev Distance – Antithesis May 16 '16 at 19:19
• (O(n³): n is O(#columns+#rows)?) I'd start at the algorithmic level: Keep a queue of boundary pieces to process. Initialise integer matrix cells with large number. Start with zero "at the ATMs", inserting each in queue. Take boundary piece from the queue, increase values "just outside", splitting boundary pieces at matrix boundaries (there's a problem here with same distance from multiple matrix boundaries), joining if encountering same value (lower shouldn't happen). If that works, it should be O(n²). (If the question is how to best code the approach presented, pls make that explicit.) – greybeard May 17 '16 at 8:55