Albert 被困在结冰的湖面上。 他想知道他是否能回到岸上。 他目前在雪堆上，这给了他一些摩擦力。但一旦他踏进冰面，他会朝同一方向滑行，直到撞上另一个雪堆。 冰面上也有他必须避开的危险的洞。
Albert 的小狗，Kuna，也被困在一个不同的雪堆上。Albert 能找到他的小狗并把它带到岸上吗？
Albert 只能水平和垂直移动。 他最终需要来到岸边，离开湖面 输入包括以下参数： side_length: 湖面的长度（这是一个正方形） lake_grid: 一个二维数组代表湖面，其中 0 代表冰面，1 代表雪堆，-1 代表洞 albert_row: Albert 所在的雪堆的行 albert_column: Albert 所在的雪堆的列 kuna_row: Kuna 所在的雪堆的行 kuna_column: Kuna 所在的雪堆的列
在线评测地址: https://www.lintcode.com/problem/lake-escape/?utm_source=sc-v2ex-fks
样例 输入: 7 [[0,0,0,0,0,0,0],[0,0,-1,0,0,0,0],[0,0,1,-1,0,-1,0],[-1,0,1,0,0,0,0],[0,1,1,0,0,1,0],[-1,0,-1,0,-1,0,0],[0,0,0,0,0,0,0]] 4 1 3 2 输出: true
说明：
如图所示。黄色格子是 Albert 的位置，红色格子是 Kuna 的位置。Albert 可以向右走到(4,2)，向上走到(3,2)，然后向右走，离开湖面。

[题解] 直接 bfs 去搜索即可 public class Solution { /** * @param side_length: the length of a side of the lake (it's a square) * @param lake_grid: a 2D matrix representing the lake 0= ice, 1= snowbank, -1= hole * @param albert_row: row of Albert's snowbank * @param albert_column: column of Albert's snowbank * @param kuna_row: row of Kuna's snowbank * @param kuna_column: column of Kuna's snowbank * @return: a bool - whether Albert can escape */ public boolean lakeEscape(int side_length, int[][] lake_grid, int albert_row, int albert_column, int kuna_row, int kuna_column) { // write your code here int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int [][][] visit = new int[2][side_length][side_length]; Queue<Integer> qx = new LinkedList<>(); Queue<Integer> qy = new LinkedList<>(); Queue<Integer> qc = new LinkedList<>(); qc.offer(0); qx.offer(albert_row); qy.offer(albert_column); while (!qx.isEmpty()){ int cc = qc.poll(); int cx = qx.poll(); int cy = qy.poll(); if (visit[cc][cx][cy] != 0) continue; visit[cc][cx][cy] = 1; for (int i = 0; i < 4; i++){ int nowx = cx, nowy = cy; boolean flag1 = true, flag2 = false, flag3 = false; for (int j = 0; j <= side_length; j++){ nowx += dx[i]; nowy += dy[i]; if (nowx == kuna_row && nowy == kuna_column) flag3 = true; if (nowx < 0 || nowx >= side_length || nowy < 0 || nowy >= side_length) { flag2 = true; break; } if (lake_grid[nowx][nowy] == -1) { flag1 = false; break; } if (lake_grid[nowx][nowy] == 1) break; } if (flag2){ if (cc == 1 || flag3) return true; } else if (flag1){ if (flag3){ qc.offer(1); qx.offer(nowx); qy.offer(nowy); } else{ qc.offer(cc); qx.offer(nowx); qy.offer(nowy); } } } } return false; } }
更多语言代码参见： https://www.jiuzhang.com/solution/lake-escape/?utm_source=sc-v2ex-fks