【传送门】http://www.lintcode.com/zh-cn/problem/portal/
import java.util.Arrays;
import java.util.LinkedList;
public class Solution {
private int res = Integer.MAX_VALUE;
/**
* @param Maze:
* @return: nothing
*/
public int Portal(char[][] Maze) {
//
int m = Maze.length;
int n = Maze[0].length;
int[][] matrix = new int[Maze.length][Maze[0].length];
for (int i = 0;
i < matrix.length;
i++) {
int[] ints = matrix[i];
Arrays.fill(ints, -1);
}
//先找到入口，step是0,然后从入口开始向四个方向扩大，使用平序遍历二叉树的方法，一层一层向外扩张
LinkedList list = new LinkedList<>();
for (int i = 0;
i < Maze.length;
i++) {
char[] chars = Maze[i];
for (int j = 0;
j < chars.length;
j++) {
char aChar = chars[j];
if (aChar == 'S') {
matrix[i][j] = 0;
list.add(new Node(j, i));
}
}
}
while (list.size() > 0) {
Node node = list.removeFirst();
int i = node.y;
int j = node.x;
int step = matrix[i][j];
//向下搜索
if (i + 1 < m && matrix[i + 1][j] == -1) {
char c = Maze[i + 1][j];
if (c == 'E') {
return step + 1;
} else if (c == '*') {
matrix[i + 1][j] = step + 1;
list.add(new Node(j, i + 1));
}
}
//向右搜索
if (j + 1 < n && matrix[i][j + 1] == -1) {
char c = Maze[i][j + 1];
if (c == 'E') {
return step + 1;
} else if (c == '*') {
matrix[i][j + 1] = step + 1;
list.add(new Node(j + 1, i));
}
}
//向上搜索
if (i - 1 >= 0 && matrix[i - 1][j] == -1) {
char c = Maze[i - 1][j];
if (c == 'E') {
return step + 1;
} else if (c == '*') {
matrix[i - 1][j] = step + 1;
list.add(new Node(j, i - 1));
}
}
//向左搜索
if (j - 1 >= 0 && matrix[i][j - 1] == -1) {
char c = Maze[i][j - 1];
if (c == 'E') {
return step + 1;
} else if (c == '*') {
matrix[i][j - 1] = step + 1;
list.add(new Node(j - 1, i));
}
}}
return -1;
}private class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}}
