iamthuypham
3/7/2018 - 7:56 PM

Closest Parking Lot - Problem Approach

``````// input parking lots and size, output closest lot
// input matrix and length
// 1 1 1 1 0
// 1 1 0 0 0
// 1 1 1 0 0
// 1 1 0 0 0
// 1 1 1 1 1
// output index of row and column
// {1,2}

// Solution: breath first search (BFS)

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Main {

public static int[] findClosest(int[][] matrix, int n, ArrayList<int[]> nextToVisit, HashMap<Integer,Integer> visited){
int[] res = {0,0};
while (!nextToVisit.isEmpty()){
int[] current = nextToVisit.remove(0);

// found
if (matrix[current[0]][current[1]] == 0){
res[0] = current[0];
res[1] = current[1];
return res ;
}

// visted contains pair value => continue next value of nextToVisit
if (visited.containsKey(current[0]) && visited.get(current[0]) == current[1] || current[0] == n-1){
continue;
}

// not contains => add to nextToVisit
visited.put(current[0], current[1]);

// for each child => recurse
int[] leftChild = {current[0]+1,current[1]};
int[] rightChild = {current[0], current[1]+1};
}
// nothing found => return false
return res;
}

public static void main(String[] args) {
int[][] matrix= {
{1,1,1,1,0},
{1,1,1,0,0},
{1,1,0,1,1},
{1,1,0,0,0},
{1,0,0,0,0}};
int n = matrix.length;

ArrayList<int[]> nextToVisit = new ArrayList<>();
HashMap<Integer,Integer> visited = new HashMap<Integer,Integer>();

// start element
int[] start = {0,0};