@yexiaoqi
2022-05-20T16:41:43.000000Z
字数 1575
阅读 495
刷题
题目:定义一个二维数组 N*M ,如 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],既第一格是可以走的路。
数据范围:2≤n,m≤10, 输入的内容只包含 0≤val≤1
输入描述:输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。
输出描述:左上角到右下角的最短路径,格式如样例所示。
链接:https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
题目要求路线,考虑使用回溯法从左上角开始,向上下左右搜索。走到终点的时候,要不就把路径换一个地方存,要不就在后面回溯时根据结束标记判断一下,否则会把路径倒着一个个删掉,前功尽弃,/(ㄒoㄒ)/~~
public class Main {
public static boolean isEnd = false;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int m = in.nextInt();
int[][] map = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
map[i][j] = in.nextInt();
}
}
//路径存储的集合
List<Pos> path = new ArrayList<>();
isEnd = false;
backtrack(map, path,0, 0);
for(Pos p : path){
System.out.println(p.toString());
}
}
}
private static void backtrack(int[][] map, List<Pos> path, int x, int y) {
//越界了
if (x<0 || x>map.length-1 || y<0 || y>map[0].length-1) return;
//撞墙了 或者 到终点了
if (map[x][y] == 1 || isEnd) return;
//结束条件
if(x==map.length-1 && y==map[0].length-1) {
path.add(new Pos(x, y));//添加终点
isEnd = true;
return;
};
map[x][y] = 1;//标记走过的点,以防倒着走回去
path.add(new Pos(x, y));
//以 x,y 为中心,向上下左右搜索
backtrack(map, path, x-1, y);
backtrack(map, path, x+1, y);
backtrack(map, path, x, y-1);
backtrack(map, path, x, y+1);
map[x][y] = 0;//回溯,恢复到之前的点的状态
if (!isEnd)//如果已经到右下角了,路径就不移除了,后面还要打印
path.remove(path.size()-1);//回溯,移除路径最后一个点
}
public static class Pos{
int x;
int y;
public Pos(int x, int y){
this.x = x;
this.y = y;
}
public String toString() {
return "("+x+","+y+")";
}
}
}
因为迷宫只有一条通道,不考虑最短路径的问题,否则需要在找到终点后比一下找出最短路径,参见网友解法