google onsite系列：走迷宫
原题：matrix迷宫最短路径的扩展，假设小球在确定一个方向后一直走直到碰到障碍物或者到了迷宫的边界才会停下来。只有当小球最终停在出口位置才算走出迷宫，计算最少需要几步走出迷宫。
思路：简单的迷宫最短路径用bfs来遍历。这题的考点是如何把小球的行走方式转换为bfs遍历中离散的“下一步”。这里想象在x或者y轴上障碍物和边界组成的线段，所有段里的点都有两个方向上的2个next。所有对于任何一个非障碍物点，其next一共有4个：x和y轴上段的边界。预处理的方法就是一行行和一列列scan，同时更新线段中所有点的两个边界。有了预处理的表以后，只需要用可计算步数的bfs即可。
基本算法：
- 预处理在一个方向上要两层loop，比如x轴，outer loop逐行，inner loop逐列。因为左右两个出口，所以只有遇到障碍或者右边界才处理所有当前线段内的点（多一层循环），最后更新left进入下一个线段。
- bfs：层次化的bfs也需要两层loop，outer loop表示处理完一层，inner loop处理同层的所有点。这样每次inner loop结束就可以increment step。
思路明确了，写code的时候还是犯了不少错误。
- x方向和y方向处理的不同：x方向扫的时候，用left和right表示当前边界。而y方向扫的时候，用up和down作为当前边界。因为matrix中的点都是按row-major的方式存储的为一个int。无论横向还是纵向预处理，都是用row index*列数+column index这个公式。所以两种处理的边界点的计算code中不是直接替换left和up，right和down的（看code就明白了）
- reset left/right/up/down：因为是逐行/列扫描，在处理下一行/列的时候要reset left/right/up/down。开始错误的只在两层循环外初始化这些变量。
/* Access log format:
50.77.59.241 - - [31/Mar/2014:09:50:57 -0700] "GET /biz/chiang-mai-thai-restaurant-minneapolis HTTP/1.1" 200 57115 <...>
*/
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args) {
int[][] matrix = { { 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0 },
{ 0, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0 } };
System.out.println(findShortestMazeExit(matrix, 0, 0, 3, 5));
}
static int findShortestMazeExit(int[][] matrix, int startx, int starty, int exitx, int exity) {
int m=matrix.length;
int n=matrix[0].length;
List<Integer>[] neighbors = fillupNeighbors(matrix);
System.out.println(Arrays.toString(neighbors));
boolean[] visited = new boolean[m*n];
Queue<Integer> q = new LinkedList<>();
int step = 0;
q.offer(startx*n+starty);
while(!q.isEmpty()) {
int qs = q.size();
for(int i=0;i<qs;i++) {
int point = q.poll();
int x = point/n;
int y = point%n;
if(x==exitx && y==exity) {
return step;
}
for(Integer nb : neighbors[point]) {
if(!visited[nb]) {
visited[nb]=true;
q.offer(nb);
}
}
}
step++;
}
return -1;
}
static List<Integer>[] fillupNeighbors(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
List<Integer>[] neighbors = (List<Integer>[]) new List[m*n];
for(int i=0;i<m;i++) {
int left = 0, right = -1;
for(int j=0;j<=n;j++) {
if(j==n || matrix[i][j]==1) {
right=j-1;
int k = left;
while(k<j) {
int point = i*n+k;
if(neighbors[point]==null) {
neighbors[point]=new ArrayList<>();
}
neighbors[point].add(i*n+left);
neighbors[point].add(i*n+right);
k++;
}
left=j+1;
}
}
}
for(int j=0;j<n;j++) {
int up = 0, down = -1;
for(int i=0;i<=m;i++) {
if(i==m || matrix[i][j]==1) {
down=i-1;
// System.out.println("i="+i+",j="+j+",up="+up+",down="+down);
int k = up;
while(k<i) {
int point = k*n+j;
if(neighbors[point]==null) {
neighbors[point]=new ArrayList<>();
}
neighbors[point].add(up*n+j);
neighbors[point].add(down*n+j);
k++;
}
up=i+1;
}
}
}
return neighbors;
}
}