题解 | #迷宫问题#
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
广度优先算法，
1、思路就是上左下右，把当前遍历到的都加到Stack中，遍历过的不用管，一直走到头了，就在Stack中pop出一个；继续
2、遍历了的就加上标记；
3、全图标记完后，方向遍历。
5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0↓↓变成这样↓↓↓↓
[10, 1, 0, 0, 0]
[11, 1, 1, 1, 17]
[11, 1, 1, 1, 17]
[12, 13, 14, 15, 16]
[13, 1, 1, 1, 17]
[0, 0, 0, 1, 18]
[13, 1, 1, 1, 17]
[0, 0, 0, 1, 18]
没什么难点，就是代码难看了点，需要优化。代码量至少减少2/3.
这个是临时写的，至少有4个地方可以优化。留给后来人。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
/**
* 广度优先算法，顺序可以是上左下右，也可以是上右下左。无论怎么走，都可以找出最短路径
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int row = 0;
int column = 0;
int[][] grid = null;
while (in.hasNext()) {
row = in.nextInt();
column = in.nextInt();
grid = new int[row][column];
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
grid[i][j] = in.nextInt();
}
}
walk(grid, new Point(0, 0), new Point(row - 1, column - 1));
if (grid != null) {
// 从右下角网上遍历
Stack<Point> all = new Stack<>();
int endValue = grid[row - 1][column - 1];
Point cPoint = new Point(row - 1, column - 1);
all.push(cPoint);
while (!(cPoint.i == 0 && cPoint.j
== 0)) {
Point p = find(grid, endValue, cPoint);
cPoint = p;
endValue -= 1;
all.push(new Point(p.i, p.j));
}
while (!all.isEmpty()) {
Point pp = all.pop();
System.out.println("("+pp.i + "," + pp.j +")");
}
}
}
}
private static Point find(int[][] grid, int endValue, Point currentPoint) {
currentPoint.goUp();
if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
Point newPoint = new Point(currentPoint.i, currentPoint.j);
currentPoint.resetUp();
return newPoint;
}
currentPoint.resetUp();
currentPoint.goLeft();
if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
Point newPoint = new Point(currentPoint.i, currentPoint.j);
currentPoint.resetLeft();
return newPoint;
}
currentPoint.resetLeft();
currentPoint.goDown();
if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
Point newPoint = new Point(currentPoint.i, currentPoint.j);
currentPoint.resetDown();
return newPoint;
}
currentPoint.resetDown();
currentPoint.goRight();
if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
Point newPoint = new Point(currentPoint.i, currentPoint.j);
currentPoint.resetRight();
return newPoint;
}
currentPoint.goRight();
return null;
}
private static class Point {
private int i, j;
public Point(int i, int j) {
this.i = i;
this.j = j;
}
@Override
public String toString() {
return "Point{" +
"i=" + i +
", j=" + j +
'}';
}
public void goUp() {
i--;
}
public void resetUp() {
i++;
}
public void goDown() {
i++;
}
public void resetDown() {
i--;
}
public void goLeft() {
j--;
}
public void resetLeft() {
j++;
}
public void goRight() {
j++;
}
public void resetRight() {
j--;
}
}
private static ArrayList<Point> hasDones = new ArrayList<>();
private static boolean isAvil(int[][] grid, Point point) {
if (point.j < 0 || point.j >= grid[0].length) {
return false;
} else return point.i >= 0 && point.i < grid.length;
}
static int point = 10;
/**
* 开始走路了。
*
* @param grid
* @param start
* @param end
*/
private static void walk(int[][] grid, Point start, Point end) {
Point currentPoint = start;
grid[start.i][start.j] = point;
Stack<Point> array = new Stack<>();
while (!currentPoint.toString().equals(end.toString())) {
point++;
lookAround(grid, currentPoint, array);
hasDones.add(currentPoint);
if (!array.isEmpty()) {
currentPoint = array.pop();
point = grid[currentPoint.i][currentPoint.j];
}
}
}
/**
* @param grid
* @param currentPoint
*/
private static void lookAround(int[][] grid, Point currentPoint, Stack<Point> array) {
currentPoint.goUp();
save(grid, currentPoint, array);
currentPoint.resetUp();
currentPoint.goLeft();
save(grid, currentPoint, array);
currentPoint.resetLeft();
currentPoint.goDown();
save(grid, currentPoint, array);
currentPoint.resetDown();
currentPoint.goRight();
save(grid, currentPoint, array);
currentPoint.resetRight();
}
private static void save(int[][] grid, Point currentPoint, Stack<Point> array) {
if (isAvil(grid, currentPoint)) {
if (grid[currentPoint.i][currentPoint.j] == 0 && !hasCo(currentPoint)) {
Point temp = new Point(currentPoint.i, currentPoint.j);
array.push(temp);
grid[currentPoint.i][currentPoint.j] = point;
}
}
}
private static boolean hasCo(Point currentPoint) {
for (int i = 0; i < hasDones.size(); i++) {
if (hasDones.get(i).toString().equals(currentPoint.toString())) {
return true;
}
}
return false;
}
}
