定义一个二维数组 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],既第一格是可以走的路。
数据范围： ， 输入的内容只包含
[编程题]迷宫问题
- 热度指数：196476 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述:
左上角到右下角的最短路径，格式如样例所示。
示例1
输入
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)
示例2
输入
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0
输出
(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4)
说明
注意：不能斜着走！！
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int maze[][] = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
maze[i][j] = in.nextInt();
}
}
int[][] seek = new int[n][m];//用于标记坐标点是否背探寻过，如果是探寻过的，则不再搜索
Stack<int[]> ans = new Stack<>();//保存走过的路径
ans.push(new int[]{0, 0});//起点
seek[0][0] = 1;
while(true) {
int[] lastPos = ans.peek();
//如果探寻的最新的点已经到达右下角，结束
if (lastPos[0] == n - 1 && lastPos[1] == m - 1) break;
//依次探寻左，上，右，下，如果四个方向都不可达，回退路径的上一个点重新探寻
if (!canArrived(0, lastPos, ans, maze, seek) &&
!canArrived(1, lastPos, ans, maze, seek) &&
!canArrived(2, lastPos, ans, maze, seek) &&
!canArrived(3, lastPos, ans, maze, seek)) {
ans.pop();
}
}
for (int[] an : ans) {
System.out.println("(" + an[0] + "," + an[1] + ")");
}
}
/**
* 判断pos点是否可以向direction方向走是否可达
* @param direction 0：向左，1：向上，2：向右，3：向下
* @param lastPos 当前位置
* @param ans 保存探寻到的路径
* @param maze 迷宫
* @param seek 是否已经探寻过
* @return
*/
public static boolean canArrived(int direction, int[] lastPos, Stack<int[]> ans, int[][] maze, int[][] seek) {
boolean canArrived = false;
int[] pos = new int[]{lastPos[0], lastPos[1]};
switch (direction) {
case 0:
pos[1] -= 1;
break;
case 1:
pos[0] -= 1;
break;
case 2:
pos[1] += 1;
break;
case 3:
pos[0] += 1;
break;
default:
break;
}
if (pos[0] < 0 || pos[0] >= maze.length || pos[1] < 0 || pos[1] >= maze[0].length) {
//越过边界
canArrived = false;
} else{
//位置合法，且未被探寻过，且可达
if (seek[pos[0]][pos[1]] != 1 && maze[pos[0]][pos[1]] == 0) {
//未被探寻过，且可达
ans.push(pos);
canArrived = true;
}
//该点置为被探寻过
seek[pos[0]][pos[1]] = 1;
}
return canArrived;
}
}
编辑于 2024-02-01 16:35:47
回复(0)
①本题不考虑多种情况,有且只有一种解,因此dfs和bfs都可以使用,dfs要注意边界的判断,bfs要注意队列的构建以及初始化;
②在多解前提下bfs有他独特的优势,可以获取到最短路径;
③相对的dfs逻辑简单,容易理解;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int hang = in.nextInt();
int lie = in.nextInt();
int[][] db = new int[hang][lie];
for (int i = 0; i < hang; i++) {
for (int j = 0; j < lie; j++) {
db[i][j] =in.nextInt();
}
}
boolean[][] flag = new boolean[hang][lie];//表示位置是否走过
StringBuilder stringBuilder = new StringBuilder();
// dfs( db,0,0, stringBuilder,flag);
bfs(db, flag);
}
private static boolean dfs(int[][] db, int hang, int lie, StringBuilder stringBuilder, boolean[][] flag) {
//边界判断
if (hang < 0 || hang >= db.length || lie < 0 || lie >= db[0].length || flag[hang][lie]) {
return false;
}
if (db[hang][lie] == 0) {
stringBuilder.append("(" + hang + "," + lie + ")\n");
//出口
if (hang == db.length - 1 && lie == db[0].length - 1) {
System.out.println(stringBuilder);
return true;
}
flag[hang][lie] = true;//标记该位置已走过
//尝试该位置下 上下左右位置是否可行
if (dfs(db, hang - 1, lie, stringBuilder, flag) || dfs(db, hang + 1, lie, stringBuilder, flag) || dfs(db, hang, lie - 1, stringBuilder, flag) || dfs(db, hang, lie + 1, stringBuilder, flag)) {
//回溯 注意这里回溯两个坐标,因为if判断中有一个是0,但对应的坐标没有没有通路,所以回溯当前坐标跟这个0的坐标
stringBuilder.delete(stringBuilder.length() - 12, stringBuilder.length());
} else {
return true;
}
}
return false;
}
private static void bfs(int[][] db, boolean[][] flag) {
int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//创建方向数组用于遍历
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(0, 0,"(" + 0 + "," + 0 + ")\n"));//初始化
flag[0][0] = true;
while (!queue.isEmpty()) {
Point point = queue.poll();//获取并删除队列中的第一个元素
int hang = point.hang;
int lie = point.lie;
//出口
if (hang == db.length - 1 && lie == db[0].length - 1) {
System.out.println(point.path);
return;
}
//四个方向遍历
for (int[] ints : direction) {
int nx = ints[0] + hang;
int ny = ints[1] + lie;
Point temp = new Point(nx, ny, point.path);
if (nx >= 0 && nx < db.length && ny >= 0 && ny < db[0].length && !flag[nx][ny] && db[nx][ny] == 0) {
temp.hang =nx;
temp.lie =ny;
temp.path = point.path +"(" + nx + "," + ny + ")\n";
queue.add(temp);
flag[nx][ny] = true;
}
}
}
}
}
class Point {
public int hang;
public int lie;
public String path;
public Point(int hang, int lie,String path) {
this.hang = hang;
this.lie = lie;
this.path =path;
}
}
发表于 2024-01-17 11:48:32
回复(0)
第一次使用BFS写代码，终于摸到一点点门槛了，很有意思，希望对后来者有一点点帮助。
BFS难点就是在于一层层遍历下去，最后找到重点了，如何得到路径呢？
我采取的方式是使用一个HashMap<String,String>，其中key为子点，value为父点。也就是在遍历过程中，是从父点走到子点。当然你也可以不这样做，我开始不明白的时候参考的就是chatgpt。它就是从第一行开始，给每个点都标记上唯一的序号，然后去记录子点和父点的关系，本质道理都一样。
代码如下：
import java.util.*;
public class T43 {
public static void main(String[] args) {
int[][] direction = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
HashMap<String, String> father = new HashMap<>();
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String[] split = str.split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int[][] grid = new int[n][m];
boolean[][] mark = new boolean[n][m];
mark[0][0] = true;
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{0, 0});
for (int i = 0; i < n; i++) {
String tempStr = sc.nextLine();
String[] temp = tempStr.split(" ");
for (int j = 0; j < n; j++) {
grid[i][j] = Integer.parseInt(temp[j]);
}
}
//BFS
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
if (x == n - 1 && y == m - 1) {
break;
}
for (int[] ints : direction) {
int nx = ints[0] + x;
int ny = ints[1] + y;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !mark[nx][ny] && grid[nx][ny] == 0) {
queue.add(new int[]{nx, ny});
mark[nx][ny] = true;
father.put("(" + nx + "," + ny + ")", "(" + x + "," + y + ")");
}
}
}
}
Stack<String> result = new Stack<>();
String key = "(" + (n - 1) + "," + (m - 1) + ")";
result.add(key);
while (true) {
String tempstr = father.get(key);
key = tempstr;
result.add(tempstr);
if (key.equals("(0,0)") ) {
break;
}
}
while (!result.isEmpty()) {
System.out.println(result.pop());
}
}
}
编辑于 2023-12-13 00:43:41
回复(1)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static String res; //最终结果
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
// 构造迷宫
int[][] arr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = in.nextInt();
}
}
StringBuilder path = new StringBuilder();
//初始坐标 0,0
backTrack(arr, 0, 0, path);
System.out.println(res);
}
// 递归回溯
private static void backTrack(int[][] arr, int x, int y, StringBuilder path) {
//跃出边界或者点位不为0则返回
if (x < 0 || x >= arr.length || y < 0 || y >= arr[0].length || arr[x][y] != 0) {
return;
}
//走到了最右下点位
if (x == arr.length - 1 && y == arr[0].length - 1) {
path.append("(" + x + "," + y + ")\n");
res = path.toString();
return;
}
//标记为已走过
arr[x][y] = 1;
path.append("(" + x + "," + y + ")\n");
backTrack(arr, x, y - 1, path); //向上
backTrack(arr, x, y + 1, path); //向下
backTrack(arr, x - 1, y, path); //向左
backTrack(arr, x + 1, y, path); //向右
//回退
path.delete(path.length() - 6, path.length());
arr[x][y] = 0;
}
}
发表于 2023-09-11 13:25:13
回复(0)
瞎琢磨的，如果有大神帮我分析下，怎么优化就好了，大家讨论下思路
import java.util.*;
public class HJ43 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) {
int n = in.nextInt();
int m = in.nextInt();
int[][] datas = new int[n][m];
List<Point> points = new ArrayList<>();
// set用来去重，检查过的点不需要再检查
Set<String> duplicateSet = new HashSet<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
datas[i][j] = in.nextInt();
}
}
// 深度遍历datas，遇到0的就是通路，遇到1就是墙壁
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
deepDatas(datas, i, j, points, duplicateSet);
}
}
// points是倒序的，反转一下
Collections.reverse(points);
points.forEach(it -> System.out.println("(" + it.x + "," + it.y + ")"));
}
}
public static boolean deepDatas(int[][] datas, int x, int y, List<Point> points, Set<String> duplicateSet) {
if (x < 0 || y < 0 || x >= datas.length || y >= datas[0].length || datas[x][y] == 1) {
return false;
}
if (!duplicateSet.add(x + ":" + y)) {
return false;
}
if (x == datas.length - 1 && y == datas[0].length - 1) {
points.add(new Point(x, y));
return true;
}
boolean deepResult;
deepResult = deepDatas(datas, x + 1, y, points, duplicateSet);
deepResult = deepResult || deepDatas(datas, x - 1, y, points, duplicateSet);
deepResult = deepResult || deepDatas(datas, x, y - 1, points, duplicateSet);
deepResult = deepResult || deepDatas(datas, x, y + 1, points, duplicateSet);
if (deepResult) {
points.add(new Point(x, y));
}
return deepResult;
}
public static class Point {
public int x;
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
发表于 2023-08-21 15:06:38
回复(0)
import java.util.*;
public class Main {
private static List<int[]> list = new ArrayList<>();
private static boolean[][] flag;
private static boolean win = false;
private static void dfs(int[][] arr,int i,int j){
// 不符合条件
if (arr[i][j]==1||flag[i][j]){
return;
}
// 找到出口
if (i==arr.length-1&&j==arr[0].length-1){
list.add(new int[]{i,j});
win = true;
return;
}
if(!win)
list.add(new int[]{i,j});
flag[i][j] = true;
if (i>0){
dfs(arr,i-1,j);
}
if (i< arr.length-1){
dfs(arr,i+1,j);
}
if (j>0){
dfs(arr,i,j-1);
}
if (j<arr[0].length-1){
dfs(arr,i,j+1);
}
if (!win){
list.remove(list.size()-1);
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] arr = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
arr[i][j] = sc.nextInt();
}
}
flag = new boolean[m][n];
dfs(arr,0,0);
for (int i = 0; i < list.size(); i++) {
System.out.println("("+list.get(i)[0]+","+list.get(i)[1]+")");
}
}
}
发表于 2023-06-03 15:08:37
回复(1)
public class Test01 {
//定义全局变量，用来收集结果
static StringBuffer sb = new StringBuffer();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int[][] arr = new int[in.nextInt()][in.nextInt()];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
arr[i][j] = in.nextInt();
}
}
dfs(arr,0,0,"");
System.out.println(sb.toString());
}
}
public static boolean dfs(int[][] arr,int i ,int j,String result){
//下标越界
if(i>arr.length-1||j>arr[0].length-1||i<0||j<0){
return false;
}
//走出迷宫，使用全局变量收集结果。
if(i==arr.length-1 && j==arr[0].length-1){
sb.append(result);
sb.append("("+i+","+j+")");
return true;
}
//如果为0，表示可以走
if(arr[i][j]==0){
//标记已走过的路
arr[i][j]=2;
//result回溯结果
if(dfs(arr,i-1,j,result+"("+i+","+j+")\n")){
return true;
}
if(dfs(arr,i+1,j,result+"("+i+","+j+")\n")){
return true;
}
if(dfs(arr,i,j-1,result+"("+i+","+j+")\n")){
return true;
}
if(dfs(arr,i,j+1,result+"("+i+","+j+")\n")){
return true;
}
//回溯
arr[i][j]=0;
}
return false;
}
}
发表于 2023-05-14 21:25:02
回复(0)
BFS用对象链表在尾节点向上打印路径，不用数组，用两个短for确定移动方向
import java.util.Scanner;
import java.util.*;;
public class Main {
public int x;
public int y;
public Main parent;
public void setValue(int x, int y, Main parent) {
this.x = x;
this.y = y;
this.parent = parent;
}
public static boolean bfs(ArrayList<Main> zt, LinkedList<Main> open,
int maze[][], int N, int M, int[][] visit) {
while (!open.isEmpty()) {//节点的上下左右只是open的一部分
int posX = open.get(0).x;
int posY = open.get(0).y;
zt.add(open.get(0));//close表存储路径
if (posX == (N - 1) && posY == (M - 1)) {
return true;
}
for (int i = -1; i < 2; i++)
for (int j = -1; j < 2; j++) {
if (i != j &&
i != -1 * j) {//满足条件的i,j组合为{-1,0},{0,-1},{1,0},{0,1}，即上下左右四个方向
posX = open.get(0).x + i;
posY = open.get(0).y + j;
if (posX < N && posX >= 0 && posY < M && posY >= 0) {
if (maze[posX][posY] == 0 && visit[posX][posY] == 0 ) {
Main migongtemp = new Main();
migongtemp.setValue(posX, posY, open.get(0));
visit[posX][posY] = 1;
open.add(migongtemp);
}
}
}
}
open.remove(0);
}
return false;
}
public static void printRoad(ArrayList<Main> zt) {
ArrayList<String> road = new ArrayList();
Main migongtemp = zt.get(zt.size() - 1);
//向前追溯路径
while (migongtemp.parent != null) {
road.add("(" + migongtemp.x + "," + migongtemp.y + ")");
migongtemp = migongtemp.parent;
}
if (migongtemp.parent == null) {
road.add("(" + migongtemp.x + "," + migongtemp.y + ")");
}
//向后打印
for (int i = road.size() - 1; i > 0; i--) {
System.out.println(road.get(i));
}
System.out.println(road.get(0));
}
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int[][] maze = new int[11][11];
int[][] visit = new int[11][11];
while (scan.hasNext()) {
ArrayList<Main> zt = new ArrayList ();//就是close 表，存路径
LinkedList<Main> open = new
LinkedList ();//bfs遍历表，存当前待遍历节点,LinkedList好删除头节点,Queue是基于LinkedList
int N = scan.nextInt();
int M = scan.nextInt();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
maze[i][j] = scan.nextInt();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visit[i][j] = maze[i][j];
}
}
Main migongtemp = new Main();
migongtemp.setValue(0, 0, null);
open.add(migongtemp);
if (bfs(zt, open, maze, N, M, visit)) {
printRoad(zt);
}
}
}
}
发表于 2023-05-11 18:18:24
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
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<Position> path = new ArrayList<>();
if(dfs(path, map, 0, 0)) {
for (Position p : path) {
System.out.println("(" + p.x + "," + p.y + ")");
}
}
}
}
public static boolean dfs(List<Position> path, int[][] map, int x, int y) {
int n = map.length;
int m = map[0].length;
if (x < 0 || y < 0 || x >= n || y >= m) {
return false;
}
if (map[x][y] == 1) return false;
if (x == n - 1 && y == m - 1) {
path.add(new Position(x, y));
return true;
}
path.add(new Position(x, y));
map[x][y] = 1;
if (dfs(path, map, x + 1, y)) return true;
if (dfs(path, map, x, y + 1)) return true;
if (dfs(path, map, x - 1, y)) return true;
if (dfs(path, map, x, y - 1)) return true;
path.remove(path.size() - 1);
map[x][y] = 0;
return false;
}
public static class Position{
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
}
发表于 2023-05-07 17:01:55
回复(0)
野路子~~~~~~~~
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static boolean isEnd; // 是否找到出口 找到则结束
static List<String> list = new ArrayList<>(); // 收集路径
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] migong = new int[scanner.nextInt()][scanner.nextInt()];
for (int i = 0; i < migong.length; i++) {
for (int j = 0; j < migong[i].length; j++) {
migong[i][j] = scanner.nextInt();
}
}
walk(migong, 0, 0);
}
public static void walk(int[][] migong, int i, int j) {
if(isEnd){
return;
}
migong[i][j] = 2; // 2表示走过
if(!list.contains("(" + i + "," + j + ")")){
list.add("(" + i + "," + j + ")");
}
if (i == migong.length - 1 && j == migong[i].length - 1) {
viewResult(list);
isEnd = true;
return;
}
int a = i + 1 < migong.length ? migong[i + 1][j] : 1;
int b = i - 1 >= 0 ? migong[i - 1][j] : 1;
int c = j + 1 < migong[i].length ? migong[i][j + 1] : 1;
int d = j - 1 >= 0 ? migong[i][j - 1] : 1;
// 如果四个位置都不为0 则把当前位置设为1不可行
if (a != 0 && b != 0 && c != 0 && d != 0) {
migong[i][j] = 1;
list.remove("(" + i + "," + j + ")");
if (a == 2) {
walk(migong, i + 1, j);
}
if (b == 2) {
walk(migong, i - 1, j);
}
if (c == 2) {
walk(migong, i, j + 1);
}
if (d == 2) {
walk(migong, i, j - 1);
}
}
if (a == 0) {
walk(migong, i + 1, j);
}
if (b == 0) {
walk(migong, i - 1, j);
}
if (c == 0) {
walk(migong, i, j + 1);
}
if (d == 0) {
walk(migong, i, j - 1);
}
}
public static void viewResult(List<String> list) {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
发表于 2023-04-20 23:31:07
回复(0)
import java.util.*;
/*
* 迷宫问题
*/
class Pair { //坐标
int x;
int y;
Pair father;
public Pair(int x, int y, Pair father) {
this.x = x;
this.y = y;
this.father = father;//前驱结点，定义这个用来保存经过的路径
}
}
public class Main {
//根据题目要求，转换输出格式
public static String toStr(int curx, int cury) {
StringBuilder sb = new StringBuilder();
sb.append("(" + curx + "," + cury + ")");
return sb.toString();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int row = sc.nextInt();
int col = sc.nextInt();
int [][]array = new int [row][col];
//输入迷宫
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
array[i][j] = sc.nextInt();
}
}
//迷宫只能走上下左右
int [][]fourLocation = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int [][] flag = new int[row][col]; //标记是否被走过
//队列用来存储迷宫的位置
Deque<Pair> queue = new LinkedList<>();
//放置路径
Stack<Pair> stack = new Stack<>();
queue.offer(new Pair(0, 0, null));
flag[0][0] = 1; //走过标记为1
int temp = 0; //判断是否在目标位置。即右下角
Pair curLocation = null;
while (!queue.isEmpty()) {
curLocation = queue.poll();
//当前位置带出所有新的位置, 可以向上下左右走
for (int i = 0; i < 4; i++) {
//计算新的位置
int curX = curLocation.x;
int curY = curLocation.y;
int newX = curX + fourLocation[i][0]; //x轴
int newY = curY + fourLocation[i][1]; //y轴
//位置越界，继续计算下一个位置
if (newX < 0 || newX >= row || newY < 0 || newY >= col) {
continue;
}
//如果新的位置无障碍并且之前也没走过，保存新的位置
if (array[newX][newY] == 0 && flag[newX][newY] == 0) {
//找到新位置和新位置前驱位置（上一个位置）
Pair newLocation = new Pair(newX, newY, curLocation);
queue.offer(newLocation);
flag[newX][newY] = 1;
}
//如果新的位置为目标位置,则结束查找
if (newX == row - 1 && newY == col - 1) {
temp = 1; //到达目标位置
break;
}
}
if (temp == 1) {
break;
}
}
//将路径入栈，先进后出原则，最后的一个位置先入栈，故而最后一个出来
while (curLocation != null) {
stack.push(curLocation);
curLocation = curLocation.father;
}
//将栈中路径按要求输出
while (!stack.isEmpty()) {
System.out.println(toStr(stack.peek().x, stack.peek().y));
stack.pop();
}
//因为是将前驱位置入栈，所以栈中位置只到目标位置的前一个位置。
System.out.println(toStr(row-1, col-1));
}
}
/*
* 迷宫问题
*/
class Pair { //坐标
int x;
int y;
Pair father;
public Pair(int x, int y, Pair father) {
this.x = x;
this.y = y;
this.father = father;//前驱结点，定义这个用来保存经过的路径
}
}
public class Main {
//根据题目要求，转换输出格式
public static String toStr(int curx, int cury) {
StringBuilder sb = new StringBuilder();
sb.append("(" + curx + "," + cury + ")");
return sb.toString();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int row = sc.nextInt();
int col = sc.nextInt();
int [][]array = new int [row][col];
//输入迷宫
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
array[i][j] = sc.nextInt();
}
}
//迷宫只能走上下左右
int [][]fourLocation = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int [][] flag = new int[row][col]; //标记是否被走过
//队列用来存储迷宫的位置
Deque<Pair> queue = new LinkedList<>();
//放置路径
Stack<Pair> stack = new Stack<>();
queue.offer(new Pair(0, 0, null));
flag[0][0] = 1; //走过标记为1
int temp = 0; //判断是否在目标位置。即右下角
Pair curLocation = null;
while (!queue.isEmpty()) {
curLocation = queue.poll();
//当前位置带出所有新的位置, 可以向上下左右走
for (int i = 0; i < 4; i++) {
//计算新的位置
int curX = curLocation.x;
int curY = curLocation.y;
int newX = curX + fourLocation[i][0]; //x轴
int newY = curY + fourLocation[i][1]; //y轴
//位置越界，继续计算下一个位置
if (newX < 0 || newX >= row || newY < 0 || newY >= col) {
continue;
}
//如果新的位置无障碍并且之前也没走过，保存新的位置
if (array[newX][newY] == 0 && flag[newX][newY] == 0) {
//找到新位置和新位置前驱位置（上一个位置）
Pair newLocation = new Pair(newX, newY, curLocation);
queue.offer(newLocation);
flag[newX][newY] = 1;
}
//如果新的位置为目标位置,则结束查找
if (newX == row - 1 && newY == col - 1) {
temp = 1; //到达目标位置
break;
}
}
if (temp == 1) {
break;
}
}
//将路径入栈，先进后出原则，最后的一个位置先入栈，故而最后一个出来
while (curLocation != null) {
stack.push(curLocation);
curLocation = curLocation.father;
}
//将栈中路径按要求输出
while (!stack.isEmpty()) {
System.out.println(toStr(stack.peek().x, stack.peek().y));
stack.pop();
}
//因为是将前驱位置入栈，所以栈中位置只到目标位置的前一个位置。
System.out.println(toStr(row-1, col-1));
}
}
发表于 2023-04-02 17:17:06
回复(0)
static LinkedList<Integer[]> goList = new LinkedList<>();
static Integer[][] arr;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
int widh = in.nextInt();
int height = in.nextInt();
arr = new Integer[height][widh];
for (int i = 0; i < widh; i ++) {
for (int j = 0; j < height; j ++) {
arr[j][i] = in.nextInt();
}
}
LinkedList<Integer[]> myList = new LinkedList<>();
myList.add(new Integer[] {0, 0});
getPath(myList);
while(!goList.isEmpty()){
Integer[] integers = goList.removeFirst();
System.out.printf("(%s,%s)",integers[1],integers[0]);
System.out.println();
}
}
}
public static void getPath(LinkedList<Integer[]> list) {
Integer[] postion = list.getLast();
if(postion[0] == arr.length-1 && postion[1] == arr[0].length-1 && (list.size()<goList.size() || goList.isEmpty())){
goList = list;
return;
}
// 向右
Integer[] newPostion = null;
if (postion[0]<arr.length-1 && isValid(list, newPostion = new Integer[] {postion[0] + 1, postion[1]})) {
LinkedList<Integer[]> myList = new LinkedList<>(list);
myList.add(newPostion);
getPath(myList);
}
// 向左
if (postion[0]>0 && isValid(list, newPostion = new Integer[] {postion[0] - 1, postion[1]})) {
LinkedList<Integer[]> myList = new LinkedList<>(list);
myList.add(newPostion);
getPath(myList);
}
// 向上
if (postion[1]>0 && isValid(list, newPostion = new Integer[] {postion[0] , postion[1]-1})) {
LinkedList<Integer[]> myList = new LinkedList<>(list);
myList.add(newPostion);
getPath(myList);
}
// 向下
if (postion[1]<arr[0].length-1 && isValid(list, newPostion = new Integer[] {postion[0], postion[1] + 1})) {
LinkedList<Integer[]> myList = new LinkedList<>(list);
myList.add(newPostion);
getPath(myList);
}
}
public static boolean isValid(LinkedList<Integer[]> list, Integer[] newPostion) {
return arr[newPostion[0]][newPostion[1]] != 1 && !list.stream().anyMatch(item -> item[0] == newPostion[0] && item[1] == newPostion[1]);
}
发表于 2023-03-29 19:19:53
回复(0)
思路：深度优先遍历 +回溯
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] elem = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
elem[i][j] = scanner.nextInt();
}
}
boolean[][] flag = new boolean[n][m];
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
dfs(elem, flag, 0, 0, list);
//一定是存在通路的
int i=0;
int len=list.size();
while (i<len) {
ArrayList<Integer> ret = list.get(i++);
System.out.println("(" + ret.get(0) + "," + ret.get(1) + ")");
}
}
private static boolean dfs(int[][] elem, boolean[][] flag, int i, int j, ArrayList<ArrayList<Integer>> list) {
if (i < 0 || i >= elem.length || j < 0 || j >= elem[0].length) {//数组越界
return false;
}
if (flag[i][j]) {//如果这个位置走过了
return false;
}
if (elem[i][j] == 0) {//如果这个位置 没有走过 而且是通路
ArrayList<Integer> ret = new ArrayList<>();
ret.add(i);
ret.add(j);
list.add(ret);
if (i == elem.length - 1 && j == elem[0].length - 1) {
//出口位置 而且出口一定是通路
return true;
}
flag[i][j] = true;
//尝试 四个方向的路径
if (!(dfs(elem, flag, i + 1, j, list) || dfs(elem, flag, i - 1, j, list) || dfs(elem, flag, i, j + 1, list) || dfs(elem, flag, i, j - 1, list))) {
//如果这结点的四个方向没有一个是可走的 那么这个结点就不可用 回溯
flag[i][j] = false;
list.remove(list.size() - 1);
} else
return true;
}
//这里 就说明 这个位置没有走过 但是 不是通路
return false;
}
}
发表于 2022-09-08 20:45:25
回复(1)
运行时间：19ms 超过88.64% 用Java提交的代码 占用内存：9628KB 超过93.21% 用Java提交的代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] mazeSize = br.readLine().split(" ");
int n = Integer.parseInt(mazeSize[0]), m = Integer.parseInt(mazeSize[1]);
int[][] maze = new int[n][m];
for (int i = 0; i < n; i++) {
String[] inputs = br.readLine().split(" ");
for (int j = 0; j < m; j++) {
maze[i][j] = Integer.parseInt(inputs[j]);
}
}
Solution sl = new Solution();
System.out.println(sl.findPath(maze, n, m));
}
}
class Solution {
int n, m;
int[][] maze;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public StringBuilder findPath(int[][] maze, int n, int m) {
this.n = n;
this.m = m;
this.maze = maze;
boolean[][] visited = new boolean[n][m];
LinkedList<Integer> path = new LinkedList<>();
dfs(path, visited, 0, 0);
int size = path.size();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
sb.append("(").append(path.get(i++)).append(", ").append(path.get(i)).append(")\n");
}
return sb;
}
public void dfs(LinkedList<Integer> path, boolean[][] visited, int row, int col) {
path.add(row);
path.add(col);
visited[row][col] = true;
if (row == n - 1 && col == m - 1) {
return;
}
for (int[] dir : dirs) {
int nr = row + dir[0], nc = col + dir[1];
if (nr >= 0 && nc >= 0 && nr < n && nc < m && !visited[nr][nc] && maze[nr][nc] == 0) {
dfs(path, visited, nr, nc);
if (visited[n - 1][m - 1]) {
return;
}
path.removeLast();
path.removeLast();
}
}
}
}
发表于 2022-09-03 16:39:18
回复(0)
//思路很清晰 迷宫 递归回溯 import java.util.*; public class Main { public static List<List<Integer>> list = new ArrayList<>();//所有通关通道 public static LinkedList<Integer> path = new LinkedList<>();//其中一条通道 public static boolean[][] flag;//判断是否走过 public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); //构建迷宫 int m = sc.nextInt();//行数 int n = sc.nextInt();//列数 int[][] arr = new int[m][n]; flag = new boolean[m][n]; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ arr[i][j] = sc.nextInt(); } } int res = m * n;//结果的长度 find(arr, 0, 0);//递归回溯查找 int k = 0;//记录最短路径的下标 //找到最短的路径 for (int i = 0; i < list.size(); i++) { if (res < list.get(i).size()) { res = list.get(i).size();//更新 k = i; } } //输出结果 for(int i = 0; i < list.get(k).size(); i += 2){ System.out.println("(" + list.get(k).get(i) +"," + list.get(k).get(i + 1) + ")"); } } //递归回溯 找出所有安全通道 public static void find(int[][] arr, int i, int j){ //越界或者走过或者有墙，返回 if (i < 0 || i >= arr.length || j < 0 || j >= arr[0].length || arr[i][j] == 1 || flag[i][j] == true) { return; } //通关则加入 if(i == arr.length - 1 && j == arr[0].length - 1){ path.add(i); path.add(j); list.add(new ArrayList<>(path)); } //上下左右，遍历 flag[i][j] = true; path.add(i); path.add(j); find( arr, i + 1, j); find( arr, i - 1, j); find( arr, i, j + 1); find( arr, i, j - 1); flag[i][j] = false; path.removeLast(); path.removeLast(); } }
发表于 2022-08-15 16:42:39
回复(1)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static boolean[][] fg;
static List<Pair> path = new ArrayList<>();
static List<Pair> res;
static int r,c;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = null;
String[] ss = br.readLine().split(" ");
r = Integer.parseInt(ss[0]);
c = Integer.parseInt(ss[1]);
int[][] map = new int[r][c];
fg = new boolean[r][c];
int k = 0;
while(k < r && (str1 = br.readLine()) != null){
String[] sc = str1.split(" ");
for(int i = 0;i < sc.length;i++){
map[k][i] = Integer.parseInt(sc[i]);
}
k++;
}
path.add(new Pair(0,0));
fg[0][0] = true;
dfs(map,0,0);
for(int i = 0;i < res.size();i++){
int a = res.get(i).x;
int b = res.get(i).y;
System.out.println("(" + a + "," + b + ")");
}
}
public static void dfs(int[][] map,int x,int y){
if(x == r - 1 && y == c - 1){
res = new ArrayList<>(path);
return;
}
if(x + 1 <= r - 1 && x + 1 >= 0 && !fg[x + 1][y] && map[x + 1][y] == 0){
path.add(new Pair(x + 1,y));
fg[x + 1][y] = true;
dfs(map,x + 1,y);
path.remove(path.size() - 1);
fg[x + 1][y] = false;
}
if(x - 1 <= r - 1 && x - 1 >= 0 && !fg[x - 1][y] && map[x - 1][y] == 0){
path.add(new Pair(x - 1,y));
fg[x - 1][y] = true;
dfs(map,x - 1,y);
path.remove(path.size() - 1);
fg[x - 1][y] = false;
}
if(y + 1 <= c - 1 && y + 1 >= 0 && !fg[x][y + 1] && map[x][y + 1] == 0){
path.add(new Pair(x,y + 1));
fg[x][y + 1] = true;
dfs(map,x,y + 1);
path.remove(path.size() - 1);
fg[x][y + 1] = false;
}
if(y - 1 <= c - 1 && y - 1 >= 0 && !fg[x][y - 1] && map[x][y - 1] == 0){
path.add(new Pair(x,y - 1));
fg[x][y - 1] = true;
dfs(map,x,y - 1);
path.remove(path.size() - 1);
fg[x][y - 1] = false;
}
}
}
class Pair{
public int x;
public int y;
Pair(int x,int y){
this.x = x;
this.y = y;
}
}
发表于 2022-08-15 16:39:36
回复(0)
tmd 5个小时！！你知道这五个小时我是怎么过的嘛！！！你知道吗！！！！
import java.util.*;
public class Main {
static List<String> op = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] mi[] = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mi[i][j] = sc.nextInt();
}
}
List<String> str = new ArrayList<>();
str.add("(0,0)");
boolean[][] v = new boolean[n][m];
v[0][0] = true;
dfs(mi, 0, 0, str, v);
for (int i = 0; i < op.size(); i++) {
System.out.println(op.get(i));
}
}
public static void dfs(int[][] mi, int n, int m, List<String> str,
boolean[][] v) {
if (mi.length == n + 1 && mi[0].length == m + 1) {
op = str;
return;
}
if (n + 1 < mi.length && mi[n + 1][m] == 0 && v[n + 1][m] == false) {
v[n + 1][m] = true;
List<String> str1 = new ArrayList<>(str);
str1.add("(" + (n + 1) + "," + m + ")");
dfs(mi, n + 1, m, str1, v);
}
if (n - 1 >= 0 && mi[n - 1][m] == 0 && v[n - 1][m] == false) {
v[n - 1][m] = true;
List<String> str2 = new ArrayList<>(str);
str2.add("(" + (n - 1) + "," + m + ")");
dfs(mi, n - 1, m, str2, v);
}
if (m + 1 < mi[0].length && mi[n][m + 1] == 0 && v[n][m + 1] == false) {
v[n][m + 1] = true;
List<String> str3 = new ArrayList<>(str);
str3.add("(" + n + "," + (m + 1) + ")");
dfs(mi, n, m + 1, str3, v);
}
if (m - 1 >= 0 && mi[n][m - 1] == 0 && v[n][m - 1] == false) {
v[n][m - 1] = true;
List<String> str4 = new ArrayList<>(str);
str4.add("(" + n + "," + (m - 1) + ")");
dfs(mi, n, m - 1, str4, v);
}
}
}
发表于 2022-08-13 06:24:53
回复(0)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
/**
* @author YXQ
* @create 2022/8/3 15:31
*/
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
int n=Integer.parseInt(str1.split(" ")[0]);
int m=Integer.parseInt(str1.split(" ")[1]);
int[][] arr=new int[n][m];
for(int i=0;i<n;i++){
String[] temp=br.readLine().split(" ");
for (int j=0;j<m;j++){
arr[i][j]=Integer.parseInt(temp[j]);
}
}
boolean[][] flag=new boolean[n][m];
dfs(arr,0,0,flag);
for(int[] aixs:res){
System.out.println("("+aixs[0]+","+aixs[1]+")");
}
}
static List<int[]> path=new ArrayList<>();
static List<int[]> res=new ArrayList<>();
public static void dfs(int[][] arr,int i,int j,boolean[][] flag){
if(i==arr.length-1&&j==arr[0].length-1&&arr[i][j]==0){
path.add(new int[]{i,j});
if(res.size()==0||res.size()>path.size())res=new ArrayList<>(path);
return;
}
if(i<0||j<0||i>arr.length-1||j>arr[0].length-1||arr[i][j]==1||flag[i][j])return;
flag[i][j]=true;
path.add(new int[]{i,j});
dfs(arr,i+1,j,flag);
dfs(arr,i,j+1,flag);
dfs(arr,i-1,j,flag);
dfs(arr,i,j-1,flag);
path.remove(path.size()-1);
flag[i][j]=false;
}
}
发表于 2022-08-03 17:03:52
回复(0)
public class Main {
private static final List<String> pathList = new LinkedList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] arr = br.readLine().split(" ");
int m = Integer.parseInt(arr[0]);
int n = Integer.parseInt(arr[1]);
boolean[][] maze = new boolean[m][n];
String[] split;
for (short i = 0; i < m; i ++) {
split = br.readLine().split(" ");
for (short j = 0; j < n; j++) {
maze[i][j] = split[j].equals("0");
}
}
boolean[][] visited = new boolean[m][n];
search(maze,
m, n,
0, 0,
visited);
for(String path : pathList) {
System.out.println(path);
}
}
private static boolean search(boolean[][] maze,
int m, int n,
int i, int j,
boolean[][] visited) {
// 标记当前坐标为已访问
visited[i][j] = true;
// 如果是终点
if (i == m - 1 && j == n - 1) {
pathList.add(0, "(" + i + "," + j + ")");
return true;
}
// 寻找合法的可进入坐标
int newI = -1, newJ = -1;
boolean accessable = false;
// go up
if (i - 1 >= 0 && maze[i - 1][j] && !visited[i - 1][j]) {
newI = i - 1;
newJ = j;
accessable = search(maze, m, n, newI, newJ, visited);
if (accessable) {
pathList.add(0, "(" + i + "," + j + ")");
return true;
}
}
// go down
if (i + 1 < m && maze[i + 1][j] && !visited[i + 1][j]) {
newI = i + 1;
newJ = j;
accessable = search(maze, m, n, newI, newJ, visited);
if (accessable) {
pathList.add(0, "(" + i + "," + j + ")");
return true;
}
}
// go left
if (j - 1 >= 0 && maze[i][j - 1] && !visited[i][j - 1]) {
newI = i;
newJ = j - 1;
accessable = search(maze, m, n, newI, newJ, visited);
if (accessable) {
pathList.add(0, "(" + i + "," + j + ")");
return true;
}
}
// go right
if (j + 1 < n && maze[i][j + 1] && !visited[i][j + 1]) {
newI = i;
newJ = j + 1;
accessable = search(maze, m, n, newI, newJ, visited);
if (accessable) {
pathList.add(0, "(" + i + "," + j + ")");
return true;
}
}
// 哪里都无法走
return false;
}
}
发表于 2022-07-16 18:08:02
回复(0)
问题信息
难度：
76条回答
4055收藏
100291浏览
通过挑战的用户
查看代码-
2023-03-11 16:31:38
-
2023-03-09 00:06:20
-
2023-03-05 12:23:54
-
2023-03-04 20:36:49 -
2023-03-04 13:41:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
