链接
描述
定义一个二维数组N*M(其中2<=N<=10;2<=M<=10),如5 × 5数组下所示:
int maze[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,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一格是可以走的路。
本题含有多组数据。
输入描述:
输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。
输出描述:
左上角到右下角的最短路径,格式如样例所示。
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
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
import java.util.*; import java.lang.*; public class Main { static int[] dx = {0, 1, 0, -1}; static int[] dy = {1, 0, -1, 0}; static int sx, sy, gx, gy; static int row, col; static final int maxn = 1005; static int[][] dis = new int[maxn][maxn]; static int[][] board; static class node { int x; int y; public node(int x, int y) { this.x = x; this.y = y; } } static node prev[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { row = sc.nextInt(); col = sc.nextInt(); board = new int[row][col]; prev = new node[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { board[i][j] = sc.nextInt(); } } sx = sy = 0; gx = row - 1; gy = col - 1; bfs(); // System.out.printf("%d%n", dis[gx][gy]); } } public static void bfs() { Queue<int[]> que = new LinkedList<>(); Deque<int[]> res = new LinkedList<>(); // 初始化 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { dis[i][j] = -1; } } que.offer(new int[]{sx, sy}); dis[sx][sy] = 0; while (!que.isEmpty()) { int[] pos = que.poll(); int x = pos[0], y = pos[1]; for (int k = 0; k < 4; k++) { int xx = x + dx[k]; int yy = y + dy[k]; if (isValid(xx, yy)) { dis[xx][yy] = dis[x][y] + 1; prev[xx][yy] = new node(x, y); que.offer(new int[]{xx, yy}); } } } int tmpx = gx, tmpy = gy; while (true) { res.push(new int[]{tmpx, tmpy}); int curx = prev[tmpx][tmpy].x; int cury = prev[tmpx][tmpy].y; tmpx = curx; tmpy = cury; if (tmpx == sx && tmpy == sy) break; } res.push(new int[]{tmpx, tmpy}); while (!res.isEmpty()) { int[] pos = res.pop(); System.out.printf("(%d,%d)%n", pos[0], pos[1]); } } public static boolean isValid(int x, int y) { if (x < 0 || x >= row || y < 0 || y >= col || board[x][y] == 1 || dis[x][y] != -1) return false; return true; } }