题:迷宫探宝,求最短距离。4×4个格子地图(1为墙,0为路,8为宝藏),由多个地图路口。
import java.util.*;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Main {
static ArrayList<ArrayList<Point>> loads = new ArrayList<>();
static int[][] direction = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
int[][] maze = {{0, 1, 1, 1}, {0, 0, 0, 1}, {1, 0, 8, 1}, {1, 0, 1, 1}};
ArrayList<Point> result = winMazeGift(maze);
System.out.println(result.size());
}
public static ArrayList<Point> winMazeGift(int[][] maze) {
// write code here
boolean[][] visited = new boolean[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (maze[i][j] == 1) visited[i][j] = true;
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if ((i == 0 || i == 3 || j == 0 || j == 3) && maze[i][j] == 0) {
subWinMazeGift(maze, i, j, visited, new ArrayList<Point>());
}
}
}
ArrayList<Point> s = loads.get(0);
for (ArrayList<Point> temp : loads) {
if (s.size() > temp.size()) {
s = temp;
}
}
return s;
}
public static void subWinMazeGift(int[][] maze, int r, int c, boolean[][] visited, ArrayList<Point> load) {
visited[r][c] = true;
Point p = new Point(r, c);
load.add(p);
if (maze[r][c] == 8) {
loads.add(new ArrayList<Point>(load));
}else{
for (int[] dir : direction) {
int new_r = r + dir[0];
int new_c = c + dir[1];
if (new_r >= 0 && new_r < 4 && new_c >= 0 && new_c < 4 && maze[new_r][new_c] != 1 && !visited[new_r][new_c]) {
subWinMazeGift(maze, new_r, new_c, visited, load);
}
}
}
load.remove(p);
visited[r][c] = false;
}
}
#笔试#