[编程题]迷宫问题
- 热度指数：225838 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入两个整数
代表迷宫的行数和列数。
行，第
行输入
个整数
代表迷宫的布局。其中，
表示单元格
是空方格，
表示单元格
输出描述:
，表示路径的第
。
出发，到达终点
，且路径上每个单元格都是空方格，行走的单元格都是彼此相邻的。
示例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.*;
public class Main {
static List<int[]> res = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
int col = in.nextInt();
int[][] nums = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
nums[i][j] = in.nextInt();
}
}
int[][] used = new int[row][col];
backtracking(nums, 0, 0, res, used);
for (int[] temp : res){
System.out.println("(" + temp[0] + "," + temp[1] + ")");
}
}
private static boolean backtracking(int[][] nums, int row, int col, List<int[]> res, int[][] used) {
res.add(new int[]{row, col});
used[row][col] = 1;
if (row == nums.length - 1 && col == nums[0].length - 1){
return true;
}
if (row + 1 < nums.length && used[row + 1][col] == 0 && nums[row + 1][col] == 0) {
if (backtracking(nums, row + 1, col, res, used)){
return true;
}
}
if (row > 0 && used[row - 1][col] == 0 && nums[row - 1][col] == 0) {
if (backtracking(nums, row - 1, col, res, used)){
return true;
}
}
if (col + 1 < nums[0].length && used[row][col + 1] == 0 && nums[row][col + 1] == 0) {
if (backtracking(nums, row, col + 1, res, used)){
return true;
}
}
if (col > 0 && used[row][col - 1] == 0 && nums[row][col - 1] == 0) {
if (backtracking(nums, row, col - 1, res, used)){
return true;
}
}
res.remove(res.size() - 1);
used[row][col] = 0;
return false;
}
}
发表于 2025-07-28 17:13:10
回复(0)
栈
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int h = in.nextInt(), w = in.nextInt();
int[][]a = new int[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
a[i][j] = in.nextInt();
}
}
int[] dx = new int [] {-1, 0, 1, 0}; // 上右下左 方向
int[] dy = new int [] {0, 1, 0, -1};
Stack<String> stack = new Stack<>(); // 栈（记录走过的每一步 x,y）
Integer x = 0, y = 0;
a[x][y] = 1;
stack.push(x + "," + y);
// 上右下左遍历，有就走 置1，无则退至前一步
while (x != h - 1 || y != w - 1) {
boolean flag = false;
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx >= 0 && tx < h && ty >= 0 && ty < w && a[tx][ty] == 0) {
x = tx;
y = ty;
a[x][y] = 1; // 走过置1
stack.push(x + "," + y); // 记录这步的位置
flag = true;
break;
}
}
// 死路回退
if (!flag) {
stack.pop(); // 弹出当前死路的一格
String[] sp = stack.peek().split(","); // 取上一步位置
x = Integer.parseInt(sp[0]);
y = Integer.parseInt(sp[1]);
}
}
// 打印路线
for (int i = 0; i < stack.size(); i++) {
System.out.printf("(%s)\n", stack.get(i));
}
}
}
发表于 2025-01-27 19:11:28
回复(0)
package com.ever; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class HJ43 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String countStr = sc.nextLine(); String[] countArr = countStr.split(" "); int x = Integer.parseInt(countArr[0]); int y = Integer.parseInt(countArr[1]); int[][] map = new int[x][y]; for (int i = 0; i < x; i++) { String[] yNumArr = sc.nextLine().split(" "); for (int j = 0; j < yNumArr.length; j++) { map[i][j] = Integer.parseInt(yNumArr[j]); } } List<int[]> indexList = getRoute(map); for (int[] index : indexList) { System.out.println("(" + index[0] + "," + index[1] + ")"); } } } private static List<int[]> getRoute(int[][] map) { List<int[]> route = new ArrayList<int[]>(); route.add(dfs(map, 0, 0, route)); Collections.reverse(route); return route; } private static int[] dfs(int[][] map, int x, int y, List<int[]> routeList) { int xLen = map.length; int yLen = map[0].length; if (x < 0 || x >= xLen || y < 0 || y >= yLen) { return null; } if (map[x][y] == 1) { return null; } if (x == xLen - 1 && y == yLen - 1) { return new int[]{x, y}; } map[x][y] = 1; List<int[]> list = new ArrayList<>(); list.add(dfs(map, x + 1, y, routeList)); list.add(dfs(map, x - 1, y, routeList)); list.add(dfs(map, x, y + 1, routeList)); list.add(dfs(map, x, y - 1, routeList)); for (int[] route : list) { if (route != null) { routeList.add(route); return new int[]{x, y}; } } return null; } }
发表于 2024-12-15 10:58:15
回复(0)
import org.junit.Test; import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; /** * @author: noob * @description : BFS的迷宫遍历 * @Date : 14:40 2024/10/17 */ public class HJ432 { private static int n = 0; private static int m = 0; private static int[][] arr; @Test public void test432() { //初始化迷宫数据 long star = System.currentTimeMillis(); n = 5; m = 5; arr = new int[n][m]; arr[1][1] = 1; arr[1][2] = 1; arr[1][3] = 1; arr[2][1] = 1; // arr[3][1] = 1; arr[3][3] = 1; arr[4][3] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { System.out.print(arr[i][j]); } System.out.println(); } List<List<String>> allpath = new ArrayList<>(); List<String> bestPath = new ArrayList<>(); List<String> checkNode = new ArrayList<>(); // 即将要走的路径, 是否检查过该节点, 是否包含过该节点; // bfs(0, 0, allpath, bestPath, checkNode); // System.out.println("共找到路径" + allpath.size()); // // bestPath.stream().forEach(System.out::println); // // // for (List<String> ty : allpath // ) { // printMazeLine(ty); // System.out.println(); // } dfs(0, 0, bestPath, checkNode); printMazeLine(bestPath); System.out.println("耗时:" + (System.currentTimeMillis() - star)); } // 2024-10-17 15:27:01 // 如果是广度搜索 则对行走的每一步每一种可能进行判断, 最后判断至出口, 则将本路径保存到 PathList中. // 如果是深度搜索 则前进一步就对当前点的可能性进行搜索, 找到出口快速移动到下一步进行判断, 如果路径不通 则回退到上一步进行判断. private static void bfs(int an, int am, List<List<String>> allpath, List<String> bestPath, List<String> checkNode) { // 进来就检查是否走过// // 检查走过的步骤放入 下面四点探测中; String pathNode = "(" + an + "," + am + ");"; bestPath.add(pathNode); checkNode.add(pathNode); if (an == n - 1 && am == m - 1) { //走到了出口 allpath.add(bestPath); return; } //如果没有走到出口 // 依次判断该点的四个方向能否到达终点 List<String> path = bestPath.stream().collect(Collectors.toList()); List<String> checkNode1 = checkNode.stream().collect(Collectors.toList()); if (an - 1 >= 0 && arr[an - 1][am] == 0 && !checkNode.contains(String.format("(%s,%s);", an - 1, am))) { bfs(an - 1, am, allpath, path, checkNode1); } if (an + 1 < n && arr[an + 1][am] == 0 && !checkNode.contains(String.format("(%s,%s);", an + 1, am))) { bfs(an + 1, am, allpath, path, checkNode1); } if (am - 1 >= 0 && arr[an][am - 1] == 0 && !checkNode.contains(String.format("(%s,%s);", an, am - 1))) { bfs(an, am - 1, allpath, path, checkNode1); } if (am + 1 < m && arr[an][am + 1] == 0 && !checkNode.contains(String.format("(%s,%s);", an, am + 1))) { bfs(an, am + 1, allpath, path, checkNode1); } // 本迭代的出口是 dian的任意方向都走不通; 或则 迭代到出口, 将本条成功的路径添加到path List中去 // 如果是全遍历 则这里不需要返回了 本路径直接结束了 // bestPath.remove(pathNode); // return bfs(an, am, allpath, bestPath, checkNode); } // 本方法有个问题 如果 下面这种格式的迷宫会造成 死循环 并且回退不回去; // 00000 // 01110 // 01000 // 00010 // 00010 // 本例的解答思路 是 按照一个路径去走 , 如果走到墙了 则返回, 并且把这次碰到墙的路径记录了下来 下次不会再次进入; // 进来的点是已经走过的, 需要判断 该点的四方向能不能走通 // 能走通则把走通本路径加上, 如果不能走通 则需要加 把 本次的点删除掉; private static void dfs(int an, int am, List<String> bestPath, List<String> checkNode) { // 进来就检查是否走过// // 检查走过的步骤放入 下面四点探测中; String pathNode = "(" + an + "," + am + ");"; bestPath.add(pathNode); checkNode.add(pathNode); if (an == n - 1 && am == m - 1) { //走到了出口 return; } //如果没有走到出口 // 方向不重要 主要是不能走回头路 if (an - 1 >= 0 && arr[an - 1][am] == 0 && !checkNode.contains(String.format("(%s,%s);", an - 1, am))) { dfs(an - 1, am, bestPath, checkNode); } else if (an + 1 < n && arr[an + 1][am] == 0 && !checkNode.contains(String.format("(%s,%s);", an + 1, am))) { dfs(an + 1, am, bestPath, checkNode); } else if (am - 1 >= 0 && arr[an][am - 1] == 0 && !checkNode.contains(String.format("(%s,%s);", an, am - 1))) { dfs(an, am - 1, bestPath, checkNode); } else if (am + 1 < m && arr[an][am + 1] == 0 && !checkNode.contains(String.format("(%s,%s);", an, am + 1))) { dfs(an, am + 1, bestPath, checkNode); } else { // 走到这里 说明本路不通 则需要回退到上一点; // 如果不能走 则需要先把这一步给回退调 bestPath.remove(bestPath.size() - 1); // 获取到进入此步的上一步, 取出数据后重新进去试一试; 注意应为要重走上一步 需要把 之前历史记录删除了再进去 String s = bestPath.remove(bestPath.size() - 1) ; an = Integer.valueOf(s.replaceAll("\\(|\\)|;", "").replaceAll("(\\d),(\\d)", "$1")); am = Integer.valueOf(s.replaceAll("\\(|\\)|;", "").replaceAll("(\\d),(\\d)", "$2")); // // dfs 需要能回到上一个点 dfs(an, am, bestPath, checkNode); } } @Test public void test(){ System.out.println(2); } private static void printMazeLine(List<String> bestPath) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (bestPath.contains(String.format("(%s,%s);", i, j))) { System.out.print(ANSI_RED + arr[i][j] + ANSI_RESET); } else { System.out.print(arr[i][j]); } } System.out.println(); } } public static final String ANSI_RED = "\u001B[31m"; public static final String ANSI_RESET = "\u001B[0m"; }
发表于 2024-10-17 17:13:07
回复(1)
import java.util.Scanner;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int rows = in.nextInt();
int cols = in.nextInt();
int[][] maze = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maze[i][j] = in.nextInt();
}
}
// 初始化
int[] start = {0, 0};
ArrayList<int[]> reached = new ArrayList<>(); // 已经走过的点
ArrayList<int[]> frontier = new ArrayList<>(); // 尚未走过的边界
frontier.add(start);
// 深度优先搜索
while (!frontier.isEmpty()) {
int[] node = frontier.remove(frontier.size()-1);
reached.add(node);
if (node[0] == rows-1 && node[1] == cols-1) break;
frontier.addAll(expand(reached, node, maze));
}
// 删去所有试错了的点（若相邻元素曼哈顿距离不为1，则删除所有中间的点）
for (int i = 1; i < reached.size(); i++) {
if (manhanton(reached.get(i), reached.get(i-1)) != 1) {
reached.remove(--i);
i--;
}
}
for (int[] p : reached) {
System.out.println("("+p[0]+","+p[1]+")");
}
}
/* 尝试走一步 */
public static ArrayList<int[]> expand(ArrayList<int[]> reached, int[] node, int[][] maze) {
ArrayList<int[]> d = new ArrayList<>();
int[] left = {node[0], node[1]-1};
int[] up = {node[0]-1, node[1]};
int[] right = {node[0], node[1]+1};
int[] down = {node[0]+1, node[1]};
int[][] move = {left, up, right, down};
for (int i = 0; i < move.length; i++) {
// 如果没碰壁、没越界、没走过，则加入frontier的后面
if (move[i][0] >= 0 && move[i][1] >= 0 &&
move[i][0] < maze.length && move[i][1] < maze[0].length &&
maze[move[i][0]][move[i][1]] != 1 && !includes(reached, move[i])) {
d.add(move[i]);
}
}
return d;
}
public static boolean includes(ArrayList<int[]> arr, int[] ele) {
for (int[] b : arr) {
if (b[0] == ele[0] && b[1] == ele[1]) {
return true;
}
}
return false;
}
public static int manhanton(int[] a, int[] b) {
// 计算两点之间的曼哈顿距离
return Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]);
}
}
发表于 2024-09-27 13:40:46
回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 注意类名必须为 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 a = in.nextInt();
int b = in.nextInt();
int[][] c = new int[a][b];
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
c[i][j] = in.nextInt();
}
}
List<String> list = new ArrayList<>();
maze(a - 1, b - 1, 0, 0, c, list);
for (int i = 1; i <= list.size(); i++) {
System.out.println(list.get(list.size() - i));
}
}
}
private static void maze(int maxA, int maxB, int a, int b, int[][] c,
List<String> list) {
if (maxA == a && maxB == b) {
list.add("(" + a + "," + b + ")");
c[a][b] = 2 ;
return;
}
c[a][b] = 1 ;
if (a + 1 <= maxA && c[a + 1][b] == 0 && c[maxA][maxB] != 2) {
maze(maxA, maxB, a + 1, b, c, list);
}
if (a - 1 >= 0 && c[a - 1][b] == 0 && c[maxA][maxB] != 2) {
maze(maxA, maxB, a - 1, b, c, list);
}
if (b + 1 <= maxB && c[a][b + 1] == 0 && c[maxA][maxB] != 2) {
maze(maxA, maxB, a, b + 1, c, list);
}
if (b - 1 >= 0 && c[a][b - 1] == 0 && c[maxA][maxB] != 2) {
maze(maxA, maxB, a, b - 1, c, list);
}
if (c[maxA][maxB] == 2) {
list.add("(" + a + "," + b + ")");
c[a][b] = 2 ;
}
}
}
发表于 2024-09-08 17:15:05
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//!!!!不使用递归，纯用栈的方式实现dfs
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int a = in.nextInt();
int b = in.nextInt();
int[][] miGong = new int[a][b];
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
miGong[i][j] = in.nextInt();
}
}
//访问过的置为1
Stack res = new Stack();
res.push(new Main().new Node(0, 0));
miGong[0][0] = 1;
while (!res.isEmpty()) {
Node s = res.peek();
int x = s.getI();
int y = s.getJ();
if(x==a-1&&y==b-1){ //意味着到达终点
break;
}
int tag = 0;
for (int i = 0; i < 4; i++) {
if (i == 0) {
if (x - 1 >= 0 && miGong[x - 1][y] != 1 && s.hasView[i] == 0) { //往上
s.hasView[i] = 1; //表示这个节点往上已经访问过了
res.push(new Main().new Node(x - 1, y)); //把新的节点放进去
miGong[x-1][y]=1;
break;
}
s.hasView[i] = 1; //表示这个节点往上已经访问过了
} else if (i == 1) {
if (x + 1 < a && miGong[x + 1][y] != 1 && s.hasView[i] == 0) { //往下
s.hasView[i] = 1; //表示这个节点往下已经访问过了
res.push(new Main().new Node(x + 1, y));
miGong[x+1][y]=1;
break;
}
s.hasView[i] = 1; //表示这个节点往下已经访问过了
} else if (i == 2) {
if (y - 1 >= 0 && miGong[x][y - 1] != 1 && s.hasView[i] == 0) { //往左
s.hasView[i] = 1; //表示这个节点往左已经访问过了
res.push(new Main().new Node(x, y - 1));
miGong[x][y-1]=1;
break;
}
s.hasView[i] = 1; //表示这个节点往左已经访问过了
} else if (i == 3) {
if (y + 1 < b && miGong[x][y + 1] != 1 && s.hasView[i] == 0) { //往右
s.hasView[i] = 1; //表示这个节点往右已经访问过了
res.push(new Main().new Node(x, y + 1));
miGong[x][y+1]=1;
break;
}
s.hasView[i] = 1; //表示这个节点往右已经访问过了
}
tag++;
}
//当for走完之后，都没有break; 意味着已经走不通了 tag==4
//直接把这个节点弹出去
if(tag==4){
miGong[x][y]=0;
res.pop();
}
}
Node[] show = new Node[res.size()];
for(int i=show.length-1;i>=0;i--){
show[i] = res.pop();
}
for(Node s : show){
System.out.println("("+s.getI()+","+s.getJ()+")");
}
}
}
class Node {
int i;
int j;
int[] hasView = new int[4];//判断这个节点某个方向是否已经访问 这个方向已经走过了
Node(int i, int j) {
this.i = i;
this.j = j;
}
int getI() {
return i;
}
int getJ() {
return j;
}
}
}
发表于 2024-07-19 03:58:40
回复(0)
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int m;
static int n;
static int[][] graph;
static int[][] offsets = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
static int[] visited;
static List<int[]> path;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
graph = new int[m][n];
path = new ArrayList<>();
visited = new int[m*n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = sc.nextInt();
}
}
visited[0] = 1;
if (dfs(0,0)) {
for (int[] point : path) {
System.out.println("(" + point[0] + "," + point[1] + ")");
}
}
}
private static boolean dfs(int i, int j) {
path.add(new int[]{i,j});
if (i==m-1 && j==n-1) {
return true;
}
for (int[] offset : offsets) {
int newX = i+offset[0];
int newY = j+offset[1];
int pos = newX * n + newY;
if (newX<0 || newX>=m || newY<0 || newY>=n
|| visited[pos]==1 || graph[newX][newY]==1) {
continue;
}
visited[pos] = 1;
if (dfs(newX, newY)) {
return true;
}
}
path.remove(path.size()-1);
return false;
}
}
发表于 2024-07-08 23:03:50
回复(0)
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
回复(2)
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)
问题信息
难度：
85条回答
4900收藏
109511浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
