FindMinimumPath.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Vector;

// args [0],[1] : index[row][col] for start postion !! value must be -1
// args [2],[3] : index[row][col] for goal postion !! value must be > 0
// but in test case, sometimes its not work for best minimum , see mark TODO

public class FindMinimumPath {
	static int []pos;
	static int []searchPath;
	static HashMap<String,Integer> path;
	static ArrayList<String> paths;
	static String pathw;

	static int arrayHistory[][] = { 
			{0,-1,-1,-1,-1,0,0},
			{0,-1,0,0,-1,0,0},
			{0,-1,0,0,4,0,0},
			{0,-1,0,0,0,0,0},
			{0,-1,0,0,0,0,0},
			{0,-1,0,0,0,0,0},
			{0,0,0,0,0,0,0},
	};
	static boolean found=false;

    public static void main(String args[]) {
		// fill visited array
		// paths = new ArrayList<>();
		path = new HashMap<>();
		paths = new ArrayList<>();
		pos=new int[]{Integer.parseInt(args[0]),Integer.parseInt(args[1])};
		searchPath=new int[]{Integer.parseInt(args[2]),Integer.parseInt(args[3])};
		System.out.println(" pos "+Arrays.toString(pos) + " val "+arrayHistory[pos[0]][pos[1]]);
		System.out.println("search : "+Arrays.toString(searchPath)+ " val "+arrayHistory[searchPath[0]][searchPath[1]]);
		pathw="";
		System.out.println("map s: "+arrayHistory.length+" : "+arrayHistory[0].length	);
		System.out.println(
			Arrays.deepToString(arrayHistory)
			.replace("[[", "[\n\t[")
			.replace("],", "],\n")
			.replace(" ", "\t")
			.replace("]]", "]\n]")
		);
        System.out.println(pathMove(pos[0], pos[1],1));
    }

    private static String pathMove(int row, int col,int counter) {
        if(found){
            return "";
		}

        if (!isInBound(row, col) || path.containsKey(row+" "+col))
            return "";
        
//         we want to make a path , that mean no index repeated
//         here we use hashmap for handling , its work perfectly
        path.put(row+" "+col,counter);

        if (row==searchPath[0] && col==searchPath[1]) {
		found=true;
		System.out.println("Found at " + row + " " + col);
		return row+","+col+" ";
        } else if (arrayHistory[row][col] == -1) {
		String val="";
		Vector<String> step=new Vector<>();
		HashMap<String,Integer[]> stepc=new HashMap<>();

// 			direction just : left, up, rigth, down             
		int[][] lookUp=new int[][]{{0,-1},{-1,0},{0,1},{1,0}};
		
		for (int[] is : lookUp) {
//              	cost have 2 value cost for row and cost for col
			Integer[] cost=new Integer[]{Math.abs(searchPath[0]-(row+is[0])),Math.abs(searchPath[1]-(col+is[1]))};

//   		        TODO - someday
// 			we need to choice minimum or closer index 
//              	the problem cost value not uniq, in this algo cost is a key of hash where the value is the next index to move,   
//              	the best way to improve is , make new function to get a cost value    
			if(stepc.containsKey(cost[0]+","+cost[1])){

				Integer row1=stepc.get(cost[0]+","+cost[1])[0];
				Integer row2=row;

				if(Math.abs(searchPath[0]-row1)>Math.abs(searchPath[0]-row2)){
					stepc.put(cost[0]+","+(cost[1]-0.5), new Integer[]{row+is[0],col+is[1]});
					step.add(cost[0]+","+(cost[1]-0.5));

				}else{
					stepc.put(cost[0]+","+(cost[1]+0.5), new Integer[]{row+is[0],col+is[1]});
					step.add(cost[0]+","+(cost[1]+0.5));
				}

			}else{
				stepc.put(cost[0]+","+cost[1], new Integer[]{row+is[0],col+is[1]});
				step.add(cost[0]+","+cost[1]);
			}
		}

		// order list 
		Collections.sort(step);
		// using order list to get hash value that contain index for searching
		for (String string : step) {
			// System.out.println(shift+" string "+string);
			Integer[]index=stepc.get(string);
			// System.out.println(shift+" index "+Arrays.toString(index));
			val=pathMove(index[0], index[1],counter+1);
			if (!val.equals("")){
				return row+","+col+" "+val;
			}
		}

        }
        return "";
    }

    private static boolean isInBound(int row, int col) {
        boolean bol = false;
        if (row < arrayHistory.length && col < arrayHistory[0].length && col >= 0 && row >= 0) {
            bol = true;
        }
		if(bol){
			if(arrayHistory[row][col]==0){
				bol=false;
			}
		}
        return bol;
    }
}