Interview Question - find minimu

有墙找路的变形 1 是路 0 是墙， 让你从左边col的任意点走到右边col的任意点的最小step。走不到就返回-1注意起始点是任意左col的点 而不是左上 ， 也不是走到右下。 要考虑到中间如果有一个col全部都是0（墙）的case

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=198749&highlight=snapchat

My code:

private int row = 0;
    private int col = 0;
    private int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int shortedPath(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return 0;
        }
        this.row = board.length;
        this.col = board[0].length;
        Queue<Position> q = new LinkedList<Position>();
        boolean[][] mark = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            if (board[i][0] == '1') {
                q.offer(new Position(i, 0, 0));
                mark[i][0] = true;
            }
        }
        
        while (!q.isEmpty()) {
            Position p = q.poll();
            if (p.y == col - 1) {
                return p.step;
            }
            for (int k = 0; k < 4; k++) {
                int next_x = p.x + dir[k][0];
                int next_y = p.y + dir[k][1];
                if (check(next_x, next_y) && !mark[next_x][next_y] && board[next_x][next_y] == '1') {
                    q.offer(new Position(p.x, p.y, p.x + 1));
                }
            }
        }
        
        return -1;
    }
    
    private boolean check(int i, int j) {
        if (i < 0 || i >= row || j < 0 || j >= col) {
            return false;
        }
        else {
            return true;
        }
    }


class Position {
    int x;
    int y;
    int step;
    Position(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}

还是 BFS， multi- end BFS

Anyway, Good luck, Richardo! -- 09/27/2016