龚秋志

用户名：uq_48078956563

访问量：55139

签　名：

等　　级
排　　名	36
经　　验	13988
参赛次数	30
文章发表	64
年　　龄	19
在职情况	学生
学　　校	湖北生物科技职业学院
专　　业	计算机应用

　　自我简介：

TA的其他文章

信息学奥赛一本通T1249- Lake Counting (BFS,DFS) java 题解
浏览：217

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

蓝桥杯2016年第七届真题-路径之谜-题解（Java代码）DFS+剪枝

　　作者: 龚秋志　　　　发表时间：2020-10-06 15:27:15 浏览：329　|　评论：1　

原题链接：蓝桥杯2016年第七届真题-路径之谜

```java
import java.awt.Checkbox;
import java.util.Arrays;
import java.util.Scanner;

public class 路径之谜 {

static int[][] arr;//地图
	static int[] dx, dy;//每个靶子要射的箭
	static int[][] direction = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//模拟4个方向
	static int n;//城堡大小

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		arr = new int[n][n];
		//初始化地图参数
		for (int i = 0, k = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] = k++;
			}
		}
		dx = new int[n];
		dy = new int[n];
		//初始化靶子的箭数
		for (int i = 0; i < n; i++) {
			dy[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			dx[i] = sc.nextInt();
		}
		//从起点出发深度搜索
		dfs(0, 0, "");
	}

/**
	 * 
	 * @param x	横坐标
	 * @param y 纵坐标
	 * @param str 路径
	 */
	public static void dfs(int x, int y, String str) {
		str += arr[x][y] + " ";//记录路径
		arr[x][y] *= -1;//这里的乘-1表示标记该点已经走过了
		//走过之后将靶子要射的箭数减一
		--dx[x];
		--dy[y];
		//剪枝    如果要射的箭数小于0了，那么就说明多射了一箭，再继续走下去就不可能符合题目的要求了  (毕竟不能跟题目对着干)
		if (dx[x] < 0 || dy[y] < 0) {
			return;
		}
		//到达终点的
		if (x == n - 1 && y == n - 1) {
			//判断射的箭数是否匹配
			if (check()) {
				System.out.println(str);
				//题目说明了测试路径唯一 那么在找到合适路径后就不用继续递归了
				//退出系统
				System.exit(0);
			}
			return;
		}
		//模拟四个方向
		for (int i = 0; i < 4; i++) {
			int x1 = x + direction[i][0];
			int y1 = y + direction[i][1];
			//边界判断
			//arr[x1][y1]>0表示没有走过这个点
			if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < n && arr[x1][y1] > 0) {
				dfs(x1, y1, str);
				//回溯
				//走过的点肯定是负数然后乘以-1就变成正数了
				arr[x1][y1] *= -1;
				//如果回溯了那说明箭的数量不对,那么就把箭重新加起来
				++dx[x1];
				++dy[y1];
			}
		}
	}
	
	//判断要射的箭数是否射完了
	public static boolean check() {
		for (int i = 0; i < n; i++) {
			//如果没射完则返回false
			if (dx[i] != 0 || dy[i] != 0) {
				return false;
			}
		}
		//射完返回true
		return true;
	}
}

```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

三人丿木丶一兀之

大佬厉害厉害

2020-10-07 15:31:42

龚秋志

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

【亲和数】（C语言代码）

C语言训练-8除不尽的数（C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

十->二进制转换（C语言代码）

蓝桥杯2016年第七届真题-路径之谜-题解（Java代码）DFS+剪枝

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-进制转换（C语言代码）

最小公倍数（C语言代码）

求组合数（C语言代码）

WU-格式化数据输出（C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

IP判断（C语言描述，蓝桥杯）

1009题解

龚秋志

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

【亲和数】 （C语言代码）

C语言训练-8除不尽的数 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

十->二进制转换 （C语言代码）

蓝桥杯2016年第七届真题-路径之谜-题解（Java代码）DFS+剪枝

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-进制转换 （C语言代码）

最小公倍数 （C语言代码）

求组合数 （C语言代码）

WU-格式化数据输出 （C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

IP判断 （C语言描述，蓝桥杯）

1009题解

【亲和数】（C语言代码）

C语言训练-8除不尽的数（C++代码）

十->二进制转换（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

最小公倍数（C语言代码）

求组合数（C语言代码）

WU-格式化数据输出（C++代码）

C语言考试练习题_保留字母（C语言代码）

IP判断（C语言描述，蓝桥杯）