求助 Java DFS 95分, #10 RE不知道什么原因
  • 板块P1238 走迷宫
  • 楼主cxcs
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/25 00:36
  • 上次更新2023/11/25 10:28:29
查看原帖
求助 Java DFS 95分, #10 RE不知道什么原因
978815
cxcs楼主2023/11/25 00:36
import java.util.Scanner;

public class Main {
	// n行  m列  t障碍数
	static int n, m;
	static int barrier[][];   // 障碍数组 行t 列数2
	static boolean st[][];	  // 状态数组, 标记是否走过
	static int endx, endy, res;	  // 终点xy    res路径数
	static int map[][], path[][];
	
	// 移动顺序: 左上右下
	static int dx[] = {0, -1, 0, 1}, 
				dy[] = {-1, 0, 1, 0};  
	
	// 当前节点 的x y坐标
	static void dfs(int x, int y, int num) {
		// 该节点 向上 右 下 左 移动
		for(int i = 0; i < 4; i++) {
			// 获取下一次移动的位置
			int a = x + dx[i], b = y + dy[i];
			
			if(a < 1 || a > n || b < 1 || b > m)  // 1开始, 数组越界
				continue;
			
			// 节点未选过
			if(!st[a][b]) {
				// 到达终点
				if(a == endx && b == endy) {  
					res += 1;
					for(int k = 1; k < num; k++) {
						System.out.print("(" + path[k][0] + "," + path[k][1] + ")->");
					}
					System.out.println("(" + endx + "," + endy + ")");
					continue;
				}
				
				// 该点是否为障碍
				if(map[a][b] != 1)
					continue;
			
				// 标记已选
				st[a][b] = true;
				path[num][0] = a;
				path[num][1] = b;
				
				dfs(a, b, num + 1);    
				// 恢复现场
				st[a][b] =false;
				path[num][0] = 0;
				path[num][1] = 0;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();    
		m = sc.nextInt();	
		
		st = new boolean[n+1][m+1];
		map = new int[n+1][m+1];
		path = new int [1000000][2];
		
		for(int i = 1; i < map.length; i++)
			for(int j = 1; j < map[0].length; j++)
				map[i][j] = sc.nextInt();
		
		int startx, starty;
		startx = sc.nextInt();
		starty = sc.nextInt();
		endx = sc.nextInt();
		endy = sc.nextInt();
		
		sc.close();
		
		// 终点是障碍物
		if(startx == endx && starty == endy) {
			System.out.println(-1);
		} else if(map[startx][starty] == 0 || map[endx][endy] == 0) {
			System.out.println(-1);
		} else {
			// 标记起点 
			st[startx][starty] = true;
			path[1][0] = startx;
			path[1][1] = starty;
			
			dfs(startx, starty, 2);   // 进入递归
			if(res > 0) {
//				System.out.println(res);
			}
			else {
				System.out.println(-1);
			}
		}
	}
}
2023/11/25 00:36
加载中...