4 BFS & Topological Algorithm

611. Knight Shortest Path

https://www.lintcode.com/problem/knight-shortest-path/description?_from=ladder&&fromId=1

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

public class Solution {
    /**
     * @param grid: a chessboard included 0 (false) and 1 (true)
     * @param source: a point
     * @param destination: a point
     * @return: the shortest path 
     */
    int row, col;
    int[] directionX = {1, 1, -1, -1, 2, 2, -2, -2};
    int[] directionY = {2, -2, 2, -2, 1, -1, 1, -1};
    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        // write your code here
        row = grid.length;
        col = grid[0].length;
        Queue<Point> queue = new LinkedList<>();
        if(grid == null || row == 0 || col == 0) return -1;
        queue.offer(source);
        int steps = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                Point curr = queue.poll();
                if(curr.x == destination.x && curr.y == destination.y) {
                    return steps;
                }
                for(int j = 0; j < 8; j++) {
                    Point nextPoint = new Point(
                        curr.x + directionX[j],
                        curr.y + directionY[j]
                    );
                    if(!inBound(nextPoint, grid)) {
                        continue;
                    }
                    queue.offer(nextPoint);
                    grid[nextPoint.x][nextPoint.y] = true;
                }
            }
            steps++;
        }
        return -1;
    }
    
    private boolean inBound(Point nextPoint, boolean[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        if(nextPoint.x >= 0 && nextPoint.x < row && nextPoint.y >= 0 && nextPoint.y < col && grid[nextPoint.x][nextPoint.y] == false) {
            return true;
        }
        return false;
    }
}

137. Clone Graph

https://www.lintcode.com/problem/clone-graph/description?_from=ladder&&fromId=1

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */


public class Solution {
    /*
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        // write your code here
        if(node == null) return null;
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        ArrayList<UndirectedGraphNode> nodes = new ArrayList<>();
        nodes.add(node);
        map.put(node, new UndirectedGraphNode(node.label));
        int start = 0;
        while(start < nodes.size()) {
            UndirectedGraphNode curr = nodes.get(start++);
            for(int i = 0; i < curr.neighbors.size(); i++) {
                if(!map.containsKey(curr.neighbors.get(i))) {
                    map.put(curr.neighbors.get(i), new UndirectedGraphNode(curr.neighbors.get(i).label));
                    nodes.add(curr.neighbors.get(i));
                }
            }
        }
        // clone neighbors
        for(int i = 0; i < nodes.size(); i++) {
            UndirectedGraphNode newNode = map.get(nodes.get(i));
            for(int j = 0; j < nodes.get(i).neighbors.size(); j++) {
                newNode.neighbors.add(map.get(nodes.get(i).neighbors.get(j)));
            }
        }
        return map.get(node);
    }
}