蓝桥杯刷题之路径之谜

题目来源

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

题意

题目中会给你两个数组，我这里是分别用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，反之为false
    static 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是否全部为0
            for(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();
    }
}