[java] [bfs] [easy]


#1

SIMPLE BFS SOLUTION IN JAVA :

public class Solution {
    
    static class Pair {
        int x;
        int y;
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    static boolean[][] visited;
    static int[][] dist;
    
    static int ans;
    
    static int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
    static int[] dy = {2, -2, 2, -2, 1, -1, -1, 1};
    
    
    public int knight(int A, int B, int C, int D, int E, int F) {
        
        dist = new int[A + 1][B + 1];
        visited = new boolean[A + 1][B + 1];
        
        boolean found = false;

        ans = Integer.MAX_VALUE;
        Pair sp = new Pair(C, D);
        Pair ep = new Pair(E, F);
        
        if(C == E && D == F)
            return 0;
        
        Queue<Pair> queue = new LinkedList<>();
        
        queue.add(sp);
        while(!queue.isEmpty()){
            Pair cp = queue.remove();
            
            for(int i = 0; i < 8; i++){
                int x = cp.x + dx[i];
                int y = cp.y + dy[i];
                if(isValid(x, y)){
                    visited[x][y] = true;
                    queue.add(new Pair(x, y));
                    dist[x][y] = dist[cp.x][cp.y] + 1;
                }
                
                if(x == ep.x && y == ep.y){
                    found = true;
                    ans = Math.min(ans, dist[x][y]);
                }
            }
        }
        
        if(!found)
            return -1;
            
        return ans;
        
    }
    
    static boolean isValid(int x, int y){
        if(x <= 0 || y <= 0 || x >= visited.length || y >= visited[0].length)
            return false;
        
        if(visited[x][y])
            return false;
        
        return true;
    }
}