蓝桥杯刷题之路径之谜

题目来源

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

题意

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

思路

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

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

代码 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();}
}