DFS-迷宫

￡神魔★判官ぃ 2023-07-11 12:48 17阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]

import java.util.Scanner;
        public class 单词2 {
        
            public static void dfs(int x,int y,int [][]arr) {
        
                if (x<1||x>n){
        
                    return;
                }
                if (y<1||y>m){
        
                    return;
                }
                if (x==x2&&y==y2&&arr[x][y]!=2){
        
                    ans++;
                    return;
                }
                if (arr[x][y]==1||arr[x][y]==2)return;//每个方格最多结果一次
                arr[x][y]=1;
                dfs(x+1,y,arr);//下
                dfs(x,y+1,arr);//右
                dfs(x-1,y,arr);//上
                dfs(x,y-1,arr);//左
                arr[x][y]=0;//回溯
    
    
            }
            static int x2,y2;
            static int n,m;
            static int ans;
            public static void main(String[] args) {
        
    
                Scanner scanner=new Scanner(System.in);
                n=scanner.nextInt();
                m=scanner.nextInt();
                int t=scanner.nextInt();
                int x1=scanner.nextInt();
                int y1=scanner.nextInt();
                x2=scanner.nextInt();
                y2=scanner.nextInt();
                int [][] arr=new int[n+1][m+1];
                for(int i=1;i<=t;i++) {
        
                    int x0=scanner.nextInt();
                    int y0=scanner.nextInt();
                    arr[x0][y0]=2;
                }
                dfs(x1,y1,arr);
                System.out.println(ans);
            }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200305202921377.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70