写完才发现这个题目 保证有且只有一条到出口的路 是我想复杂了 QAQ
import java.util.*;
/**
* @author hll[yellowdradra@foxmail.com]
* @date 2022-10-09 14:43
**/
public class Main {
/**
* 上
*/
final static int TOP = 0;
/**
* 右
*/
final static int RIGHT = 1;
/**
* 下
*/
final static int BOTTOM = 2;
/**
* 左
*/
final static int LEFT = 3;
/**
* 迷宫行数
*/
static int N;
/**
* 迷宫列数
*/
static int M;
/**
* 迷宫数组 为true表示能走 false表示不能走
*/
static boolean[][] maze;
/**
* 存储所有的路径
*/
static List<Set<Point>> paths = new ArrayList<>();
/**
* 终点
*/
static Point END_POINT;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
M = in.nextInt();
maze = new boolean[N][M];
END_POINT = new Point(N - 1, M - 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
maze[i][j] = in.nextInt() == 0;
}
}
// Set保证没有环形路径 环形路径会导致死循环
// LinkedHashSet保证输入顺序
Set<Point> p = new LinkedHashSet<>();
go(new Point(0, 0), p);
for (Set<Point> path : paths) {
// 路径的末尾是终点的话 那这是一条可行路径 打印这条路径
if (path.contains(END_POINT)) {
path.forEach(System.out::println);
}
}
}
/**
*
* @param point 目标点
* @param path 到目标点之前的路径
*/
static void go(Point point, Set<Point> path) {
Set<Point> newPath = new LinkedHashSet<>(path);
newPath.add(point);
// 如果到了终点 则立即停止探索 将路径添加至路径列表
if (point.equals(END_POINT)) {
paths.add(newPath);
return;
}
boolean isEndPoint = true;
// 顺时针探索是否有可以前进的点
for (int d = TOP; d <= LEFT; d++) {
Point nextPoint = nextPoint(point, d, newPath);
if (nextPoint != null) {
isEndPoint = false;
go(nextPoint, newPath);
}
}
// 如果没有可以前进的点 那么本次探索结束
if (isEndPoint) {
paths.add(newPath);
}
}
/**
* @param point 当前所处点位
* @param direction 探索方向
* @param path 已经走过的路径
* @return
*/
static Point nextPoint(Point point, int direction, Set<Point> path) {
int n = point.x, m = point.y;
boolean isOverBorder = false;
switch (direction) {
case TOP:
isOverBorder = --n < 0;
break;
case RIGHT:
isOverBorder = ++m >= M;
break;
case BOTTOM:
isOverBorder = ++n >= N;
break;
case LEFT:
isOverBorder = --m < 0;
break;
default:
break;
}
Point nextPoint = new Point(n, m);
// 如果 没有超出迷宫边界 && 该点位不是墙 && 没有走过该点 则这个点是可达的
if (!isOverBorder && maze[n][m] && !path.contains(nextPoint)) {
return nextPoint;
}
return null;
}
/**
* 因为要将这个Point类放进Set 所以要重写equals和hashcode方法
* 顺便重写一些toString方法 方便输出 牛客的JDK是1.8 高版本的JDK可以用Record实现Point 更简便
*/
static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + x + "," + y + ")";
}
@Override
public boolean equals(Object obj) {
Point p = (Point) obj;
if (p.x == this.x && p.y == this.y) {
return true;
}
return false;
}
@Override
public int hashCode() {
return this.toString().hashCode();
}
}
}
--------------------------------2024-07-11 更新分割线----------------------------
今天无事 摸鱼中 重写了这道题 用的jdk17
/**
* <a href="https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc">迷宫问题</a>
*
* @author hll[yellowdradra@foxmail.com]
* @since 2024/07/11
*/
public record Point(int x, int y) {
/**
* 按照题目要求的格式输出路径上的每个点
* @return 点
*/
@Override
public String toString() {
return "(" + x + "," + y + ")";
}
}
/**
* <a href="https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc">迷宫问题</a>
* <p>方向</p>
*
* @author hll[yellowdradra@foxmail.com]
* @since 2024/07/11
**/
public enum Direction {
/** 向上 */
UP,
/** 向下 */
DOWN,
/** 向左 */
LEFT,
/** 向右 */
RIGHT
}
import lombok.Data;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
/**
* <a href="https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc">迷宫问题</a>
* <p>迷宫</p>
*
* @author hll[yellowdradra@foxmail.com]
* @since 2024/07/11
**/
@Data
public class Maze {
/** 不可以走的墙 */
private static final int WALL = 1;
/** 可以走的路 */
private static final int ROAD = 0;
/** 迷宫行数 */
private final int n;
/** 迷宫列数 */
private final int m;
/** 迷宫数组 true: 能走 false: 不能走 */
private final Integer[][] map;
/** 存储所有的路径 */
private final List<Set<Point>> paths;
/** 终点 */
private final Point endPoint;
public Maze(int n, int m, Integer[][] map) {
this.n = n;
this.m = m;
this.map = map;
this.paths = new ArrayList<>();
this.endPoint = new Point(n - 1, m - 1);
// LinkedHashSet Linked保证每个点的顺序 Set保证不重复走一个点
search(new Point(0, 0), new LinkedHashSet<>());
}
/**
* 数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
*/
public void printRightPath() {
for (Set<Point> path : getPaths()) {
// 路径的末尾是终点的话 那这是一条可行路径 打印这条路径
if (path.contains(getEndPoint())) {
path.forEach(System.out::println);
}
}
}
/**
* @param point 目标点
* @param path 到目标点之前的路径
*/
private void search(Point point, Set<Point> path) {
Set<Point> newPath = new LinkedHashSet<>(path);
newPath.add(point);
// 如果到了终点 则立即停止探索 将路径添加至路径列表
if (point.equals(getEndPoint())) {
getPaths().add(newPath);
return;
}
boolean isEndPoint = true;
// 向每个方向探索
for (Direction direction : Direction.values()) {
Point nextPoint = nextPoint(point, direction, newPath);
if (nextPoint != null) {
isEndPoint = false;
search(nextPoint, newPath);
}
}
// 如果没有可以前进的点 那么本次探索结束
if (isEndPoint) {
getPaths().add(newPath);
}
}
/**
* @param point 当前所处点位
* @param direction 探索方向
* @param path 已经走过的路径
* @return 如果下一个点存在则返回下一个点 否则返回 null
*/
private Point nextPoint(Point point, Direction direction, Set<Point> path) {
int x = point.x(), y = point.y();
boolean isOverBorder = false;
switch (direction) {
case UP:
isOverBorder = --x < 0;
break;
case RIGHT:
isOverBorder = ++y >= this.m;
break;
case DOWN:
isOverBorder = ++x >= this.n;
break;
case LEFT:
isOverBorder = --y < 0;
break;
default:
break;
}
Point nextPoint = new Point(x, y);
// 如果 没有超出迷宫边界 且 该点位不是墙 且 没有走过该点 则这个点是可达的
if (!isOverBorder && map[x][y] == ROAD && !path.contains(nextPoint)) {
return nextPoint;
}
return null;
}
}
import java.util.*;
/**
* <a href="https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc">迷宫问题</a>
*
* @author hll[yellowdradra@foxmail.com]
* @since 2024/07/11
**/
public class HJ43 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
Maze maze = new Maze(n, m, ScannerUtils.scanInt2DArray(in, n, m));
maze.printRightPath();
}
}
每次写从scanner接收输入的代码太麻烦了 写了个工具类
import lombok.experimental.UtilityClass;
import java.lang.reflect.Array;
import java.util.Scanner;
/**
* 扫描器工具类
*
* @author hll
* @since 2024/07/10
*/
@UtilityClass
public class ScannerUtils {
public <T> T[] scanArray(Scanner sc, Class<T> clazz) {
return scanArray(sc, clazz, sc.nextInt());
}
@SuppressWarnings("unchecked")
public <T> T[] scanArray(Scanner sc, Class<T> clazz, int n) {
T[] array = (T[]) Array.newInstance(clazz, n);
for (int i = 0; i < n; i++) {
String val = sc.next();
if (clazz == String.class) {
array[i] = (T) val;
} else if (clazz == Integer.class) {
array[i] = (T) Integer.valueOf(val);
}
}
return array;
}
public Integer[][] scanInt2DArray(Scanner sc, int rows, int cols) {
Integer[][] array = new Integer[rows][];
for (int i = 0; i < rows; i++) {
array[i] = scanArray(sc, Integer.class, cols);
}
return array;
}
}
京公网安备 11010502036488号