50分,球助,救救孩子吧
  • 板块P1605 迷宫
  • 楼主huitaiyang
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/28 01:05
  • 上次更新2024/1/28 10:17:54
查看原帖
50分,球助,救救孩子吧
1260934
huitaiyang楼主2024/1/28 01:05
import java.util.*;
/*
输入
2 2 1 ------> 2*2的迷宫 有1个障碍
1 1 2 2 ------>起点坐标(1,1) 终点坐标(2,2)
1 2 ------>(障碍物坐标)
问:从起点到终点有多少种方法
*/
public class Main {
    static Scanner sc=new Scanner(System.in);
    static int n=sc.nextInt(),m=sc.nextInt(),t=sc.nextInt(),x0,y0,x1,y1; //n长 m宽
    static int[][] data=new int[m+1][n+1];//障碍物设为2 做过设成1 没走过为0
    static int res=0;
    public static void main(String[] args) {
        x0=sc.nextInt();
        y0=sc.nextInt();
        x1=sc.nextInt();
        y1=sc.nextInt();
        for(int i=0;i<t;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            data[a][b]=2; //障碍物设为2
        }
        dfs(x0,y0);
        System.out.println(res);
    }
    static void dfs(int x,int y){
        int[] a={1,-1,0,0}; //四个方向
        int[] b={0,0,1,-1};
        for(int i=0;i<4;i++){
            int new_x=x+a[i],new_y=y+b[i];
            if(new_x<0 || new_x>n || new_y<0 || new_y>m){ //不能越界
                continue;
            }
            if(data[new_x][new_y]==2){ //有障碍物,不走
                continue;
            }
            if(data[new_x][new_y]==1){ //不重复走
                continue;
            }
            if(new_x==y1 && new_y==y1){
                res++;
                return;
            }
            data[new_x][new_y]=1;//走过设为1
            dfs(new_x,new_y);
        }


    }
}

2024/1/28 01:05
加载中...