CareerCup

Paint fill + cache of the path + backtracking, keep min path in a global list.

I feel DFS approach will solve the problem here as the intermediate results (ex: a string indicating the path) get stored on the system memory through recursive calls. And when we hit the destination, we return boolean (true else false) value based on which we get back with status whether the destination is reached or not and the result will contain the path.

Correct me i interpreted the question wrong!

Since we do not know the location of 3 and there is no weight on route, I used Breath Search First. Otherwise, Dijkstra or Bellman-Ford as we learned on communication networks...
I used a matrix to track the parent of each node. I thought on using a list associated with each pendent to visit node and mark the visited in the same matrix (e.g. 4). Actually I think it use less memory with the "parent" list instead of matrix....

import java.util.LinkedList;

public class Snake{
	static int N = 6;
	static int M = 6;
	int[][] matrix = new int[N][M];
	Pair[][] mark = new Pair[N][M];


	class Pair{
		public int x;
		public int y;
		public Pair(int xVal,int yVal){
			x = xVal;
			y = yVal;
		}
	}

	public static void main(String[] args){
		Snake sn = new Snake();
		sn.matrix[0] = new int[]{1,1,1,1,1,1};
		sn.matrix[1] = new int[]{1,0,0,0,0,1};
		sn.matrix[2] = new int[]{1,0,1,1,1,1};
		sn.matrix[3] = new int[]{1,0,1,0,0,0};
		sn.matrix[4] = new int[]{1,0,1,1,3,0};
		sn.matrix[5] = new int[]{1,0,0,0,0,0};

		sn.findRoute();
	}
	
	public  void findRoute(){
		LinkedList<Pair> visitList = new LinkedList<Pair>();
		visitList.addFirst(new Pair(0,0));
		mark[0][0] = new Pair(0,0);
		Pair found;
		while(!visitList.isEmpty()){
			Pair pair = visitList.removeLast();
			found = getNeighbords(pair.x,pair.y,pair,visitList);
			if(found != null){
				trace(found);
				break;
			}
		}
	}
	public  void trace(Pair dest){
		int x = dest.x;
		int y = dest.y;
		Pair parent;
		while(!(x == 0 && y == 0)){
			System.out.println(x+" : "+y); 
			parent = (mark[x][y]);
			x = parent.x;
			y = parent.y;
		}
	}

	public  Pair getNeighbords(int x,int y,Pair parent,LinkedList<Pair> queue ){
		//Horizontal range
		int xMin = Math.max(x-1, 0);
		int xMax = Math.min(x+1,M-1);
		int yMin = Math.max(y-1,0);
		int yMax = Math.min(y+1,N-1);
		for(int xp = xMin; xp <= xMax; xp++){
			for(int yp = yMin; yp <= yMax; yp++){
				//visited?
				if(mark[xp][yp] != null)
					continue;

				mark[xp][yp] = parent;

				//passable?
				if(matrix[xp][yp] == 1){
					queue.addFirst(new Pair(xp,yp));
				}
				//goal?
				if(matrix[xp][yp] == 3){
					System.out.println("found: "+x+":"+y);
					return new Pair(xp,yp);
				}
			}
		}
		return null;
	}
}

/*
Thought:
1) Using BFS
2) Find dest first, using A*
*/

import java.util.LinkedList;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Collections;

class PathStep {
	int i, j;
	PathStep prev;

	public PathStep(int i, int j, PathStep prev) {
		this.i = i;
		this.j = j;
		this.prev = prev;
	}

	public String toString() {
		return "[" + i + ", " + j + "]";
	}
}

class Main {
	// BFS
	public static void shortestPath(int[][] matrix) {
		int N = matrix.length;
		// initial
		PathStep step = new PathStep(0, 0, null);
		LinkedList<PathStep> queue = new LinkedList<PathStep>();
		queue.add(step);
		// using set to check if already traversed
		HashSet<Integer> set = new HashSet<Integer>();
		boolean findDest = false;
		while(!queue.isEmpty() && !findDest) {
			LinkedList<PathStep> tmpQueue = new LinkedList<PathStep>();
			while(!queue.isEmpty()) {
				step = queue.remove();
				int i = step.i, j = step.j, id;
				if(matrix[i][j] == 3) {	// find dest
					findDest = true;
					break;
				}
				PathStep next;
				// move left
				if(j > 0 && matrix[i][j - 1] != 0) {
					id = N * i + (j - 1);
					if(!set.contains(id)) {
						set.add(id);
						next = new PathStep(i, j - 1, step);
						tmpQueue.add(next);
					}
				}
				// move right
				if(j < N - 1 && matrix[i][j + 1] != 0) {
					id = N * i + (j + 1);
					if(!set.contains(id)) {
						set.add(id);
						next = new PathStep(i, j + 1, step);
						tmpQueue.add(next);
					}
				}
				// move up
				if(i > 0 && matrix[i - 1][j] != 0) {
					id = N * (i - 1) + j;
					if(!set.contains(id)) {
						set.add(id);
						next = new PathStep(i - 1, j, step);
						tmpQueue.add(next);
					}
				}
				// move down
				if(i < N - 1 && matrix[i + 1][j] != 0) {
					id = N * (i + 1) + j;
					if(!set.contains(id)) {
						set.add(id);
						next = new PathStep(i + 1, j, step);
						tmpQueue.add(next);
					}
				}
			}
			queue = tmpQueue;
		}
		if(findDest) {
			// build path
			ArrayList<PathStep> path = new ArrayList<PathStep>();
			while(step != null) {
				path.add(step);
				step = step.prev;
			}
			Collections.reverse(path);
			// print path
			for(int i = 0; i < path.size(); i++) {
				if(i == path.size() - 1) {
					System.out.println(path.get(i));
				}
				else {
					System.out.print(path.get(i) + " -> ");
				}
			}
		}
	}

	public static void main(String[] args) {
		int[][] matrix = {
			{1,1,1,1,1,1,1,1},
			{1,0,0,0,0,0,0,1},
			{1,1,0,0,0,0,0,1},
			{0,1,1,1,0,0,0,1},
			{0,0,0,1,0,0,0,1},
			{1,1,1,1,0,0,0,1},
			{1,0,0,0,0,0,0,1},
			{3,1,1,1,1,1,1,1}
		};
		shortestPath(matrix);
	}
}

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

void printPath(int prev[], int dest, int dist, int n) {
  stack<int> st;

  while (dest != 0) {
    st.push(dest);
    dest = prev[dest];
  }
  
  cout<< "Shortest distance to destination is: " << dist << " steps."<<endl;
  cout << "0,0 => ";
  while (!st.empty()) {
    dest = st.top();
    st.pop();
    cout << dest/n<<","<<dest%n;
    if(!st.empty())
      cout<<" => ";
  }
  cout << endl;
}

void shortestPath(int mat[100][100], int n) {
  int d[n*n];
  int prev[n*n];
  for(int i=0; i< n*n; ++i) {
    d[i] = n*n+1;
    prev[i] = -1;
  }
  d[0] = 0;
  queue<int> q;
  q.push(0);
  bool reached = false;
  while(!q.empty() && !reached) {
    int curr = q.front();
    int row = curr/n;
    int col = curr%n;
    if(mat[row][col] == 3){
      // reached destination
      reached = true;
      break;
    }
    q.pop();
    int next;
    // go UP
    if(row>0 && mat[row-1][col] != 0){
      next = (row-1)*n + col;
      if(d[next] > d[curr]+1){
        d[next] = d[curr]+1;
        prev[next] = curr;
        q.push(next);
      }
    }
    //go DOWN
    if(row < n-1 && mat[row+1][col] != 0){
      next = (row+1)*n + col;
      if(d[next] > d[curr]+1){
        d[next] = d[curr]+1;
        prev[next] = curr;
        q.push(next);
      }
    }
    //go LEFT
    if(col > 0 && mat[row][col-1] != 0){
      next = row*n + col-1;
      if(d[next] > d[curr]+1){
        d[next] = d[curr]+1;
        prev[next] = curr;
        q.push(next);
      }
    }
    //go RIGHT
    if(col < n-1 && mat[row][col+1] != 0){
      next = row*n + col+1;
      if(d[next] > d[curr]+1){
        d[next] = d[curr]+1;
        prev[next] = curr;
        q.push(next);
      }
    }
  }

  if(reached){
    printPath(prev, q.front(), d[q.front()], n);
  }
}

int main() {
  int mat[100][100] = {{1,1,1,1,1,0},
                       {1,1,0,0,1,0},
                       {0,1,1,1,1,0},
                       {1,1,0,3,1,0},
                       {1,1,1,1,1,1},
                       {0,0,0,0,0,0}};

  shortestPath(mat, 6);
}

package google;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class ShortestPath {
    public static List<Field> findShortestPath(int[][] area) {
        Field[][] fields = new Field[area.length][area[0].length];
        for (int i = 0; i < fields.length; i++) {
            for (int j = 0; j < fields[0].length; j++) {
                if (area[i][j] != 0) {
                    fields[i][j] = new Field(i, j, Integer.MAX_VALUE, null);
                }
            }
        }

        LinkedList<Field> q = new LinkedList<>();

        Field start = fields[0][0];
        start.dist = 0;
        q.add(start);

        Field dest = null;
        Field cur;
        while ((cur = q.poll()) != null) {
            if (area[cur.x][cur.y] == 3) {
                dest = cur;
            }
            visitNeighbour(fields, q, cur.x - 1, cur.y, cur);
            visitNeighbour(fields, q, cur.x + 1, cur.y, cur);
            visitNeighbour(fields, q, cur.x, cur.y - 1, cur);
            visitNeighbour(fields, q, cur.x, cur.y + 1, cur);
        }

        if (dest == null) {
            return Collections.emptyList();
        } else {
            LinkedList<Field> path = new LinkedList<>();
            cur = dest;
            do {
                path.addFirst(cur);
            } while ((cur = cur.prev) != null);

            return path;
        }
    }

    private static void visitNeighbour(Field[][] fields, LinkedList<Field> q, int x, int y, Field parent) {
        int dist = parent.dist + 1;
        if (x < 0 || x >= fields.length || y < 0 || y >= fields[0].length || fields[x][y] == null) {
            return;
        }
        Field cur = fields[x][y];
        if (dist < cur.dist) {
            cur.dist = dist;
            cur.prev = parent;
            q.add(cur);
        }
    }

    private static class Field implements Comparable<Field> {
        public int x;
        public int y;
        public int dist;
        public Field prev;

        private Field(int x, int y, int dist, Field prev) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.prev = prev;
        }

        @Override
        public int compareTo(Field o) {
            return dist - o.dist;
        }
    }

    public static void main(String[] args) {
        int[][] area = new int[][] {
                {1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 0, 1},
                {1, 0, 0, 0, 1, 1},
                {1, 1, 1, 3, 1, 1},
                {0, 0, 0, 0, 0, 0}
        };
        List<Field> shortestPath = findShortestPath(area);
        for (Field f : shortestPath) {
            System.out.println(String.format("(%d;%d)", f.x, f.y));
        }
    }
}

In fact, I just tested my code. Turned out the cache is not working. It only stores the first path it has found. How should I fix this cache? If I took out the cache, the code works fine and is able to find the shortest path.

A* algorithm.