有墙找路的变形 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
