蓝桥杯刷题之路径之谜

2024-03-28 08:20
文章标签 路径 蓝桥 之谜 杯刷题

本文主要是介绍蓝桥杯刷题之路径之谜,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目来源

路径之谜
不愧是国赛的题目

题意

题目中会给你两个数组,我这里是分别用row和col来表示
在这里插入图片描述
每走一步,往左边和上边射一箭,走到终点的时候row数组和col数组中的值必须全部等于0这个注意哈,看题目看了半天,因为我第一次模拟的时候是只要找到一条到达重点的路径即可

思路

我用dfs来写的,模板就不写了,就说一下需要注意的点

  1. 到终点的时候,row和col必须全部等于0
  2. 起点的时候也要向上面和左边射一箭

代码 dfs

import java.util.*;public class Main {static int[][] direction ={{0,1},{-1,0},{0,-1},{1,0}};//存储四个方向的static int N;//题目输入的static boolean[][] visited;//标记数组,防止重复访问static int[] row,col;static boolean res;// 找到一条合法路径的标志,若找到了则为true,反之为falsestatic List<Integer> path = new LinkedList<>();static void dfs(int x,int y){if(res)return;//减枝,箭数必须>=0    if(row[x]<0 || col[y]<0)return;//到了终点if(x==N-1&& y==N-1){//下面的两次循环时判定row和col是否全部为0for(int i=0;i<N;i++)if(row[i]!=0)return;for(int i=0;i<N;i++)if(col[i]!=0)return;for(Integer num: path)System.out.print(num+" ");System.out.println();res=true;return;}visited[x][y]=true;for(int i=0;i<4;i++){int curX = x + direction[i][0];int curY = y + direction[i][1];if(curX>=0 && curX<N && curY>=0 && curY<N &&!visited[curX][curY]){visited[curX][curY] = true;row[curX]--;col[curY]--;path.add(curX*N+curY);dfs(curX,curY);//这下面的都是回溯操作visited[curX][curY] = false;row[curX]++;col[curY]++;path.remove(path.size()-1);}}}public static void main(String[] args) {Scanner s = new Scanner(System.in);N = s.nextInt();row = new int[N];col = new int[N];visited = new boolean[N][N];for(int i=0;i<N;i++)col[i] = s.nextInt();for(int j=0;j<N;j++)row[j] = s.nextInt();path.add(0);//0要加上哦// 起点也要向北和向左射一箭row[0]--;col[0]--;dfs(0,0);s.close();}
}

代码 bfs

周总结的时候再来尝试一次

这篇关于蓝桥杯刷题之路径之谜的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/855024

相关文章

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

图的最短路径算法——《啊哈!算法》

图的实现方式 邻接矩阵法 int[][] map;// 图的邻接矩阵存储法map = new int[5][5];map[0] = new int[] {0, 1, 2, 3, 4};map[1] = new int[] {1, 0, 2, 6, 4};map[2] = new int[] {2, 999, 0, 3, 999};map[3] = new int[] {3, 7

vcpkg子包路径批量获取

获取vcpkg 子包的路径,并拼接为set(CMAKE_PREFIX_PATH “拼接路径” ) import osdef find_directories_with_subdirs(root_dir):# 构建根目录下的 "packages" 文件夹路径root_packages_dir = os.path.join(root_dir, "packages")# 如果 "packages"

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

jmeter依赖jar包找不到类路径

这两天我在纠结这个问题,为啥我maven打包放在jmeter路径下后,jmeter的bean Shell 就是找不到这个类。纠结很久解开了。我记录下,留给后来的朋友。   Error invoking bsh method: eval Sourced file: inline evaluation of: ``import org.apache.jmeter.protocol.http.s

运行.bat文件,如何在Dos窗口里面得到该文件的路径

把java代码打包成.jar文件,编写一个.bat文件,执行该文件,编译.jar包;(.bat,.jar放在同一个文件夹下) 运行.bat文件,如何在Dos窗口里面得到该文件的路径,并运行.jar文件: echo 当前盘符:%~d0 echo 当前路径:%cd% echo 当前执行命令行:%0 echo 当前bat文件路径:%~dp0 echo 当前bat文件短路径:%~sdp0 nc