洛谷P1002过河卒

逻辑没问题,运行超时,得分60

写注释了,不多解释

import java.util.Scanner;

public class D1 {
    static int a,b,c,d,con; //棋盘大小 马的位置
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        a=sc.nextInt();
        b=sc.nextInt();
        c=sc.nextInt();
        d=sc.nextInt();
        con=0;  //到达终点的次数

        //初始化棋盘
        int[][] qp=new int[a+1][b+1];
        for (int i = 0; i < a+1; i++) {
            for (int j = 0; j < b+1; j++) {
                qp[i][j]=0;
            }
        }
        //马能跳到的位置如果合法 设置为马的控制区(避免马在边缘 棋盘下标越界)
        qp[c][d]=1;
        if (!(c-2<0||d-1<0)){
            qp[c-2][d-1]=1;
        }
        if (!(c-2<0||d+1>b)){
            qp[c-2][d+1]=1;
        }
        if (!(c-1<0||d-2<0)){
            qp[c-1][d-2]=1;
        }
        if (!(c-1<0||d+2>b)){
            qp[c-1][d+2]=1;
        }
        if (!(c+1>a||d-2<0)){
            qp[c+1][d-2]=1;
        }
        if (!(c+1>a||d+2>b)){
            qp[c+1][d+2]=1;
        }
        if (!(c+2>a||d-1<0)){
            qp[c+2][d-1]=1;
        }
        if (!(c+2>a||d+1>b)){
            qp[c+2][d+1]=1;
        }

        //开始递归回溯
        D1 d=new D1();
        d.xl(qp,0,0);
        //输出结果
        System.out.println(con);

    }

    //自动寻路
    private boolean xl(int[][] qp,int i,int j){
        //如果到达终点,回溯并重置为0 到达次数+1
        if (qp[a][b]==2){
            qp[a][b]=0;
            con++;
            return false;
        }
        //如果当前位置合法,标记为2,递归下一个位置
        if (pd(qp,i,j)){
            qp[i][j]=2;
            if (xl(qp,i+1,j)){
                qp[i][j]=0;
                return false;
            }else if (xl(qp,i,j+1)){
                qp[i][j]=0;
                return false;
            }
            qp[i][j]=0;
        }
        return false;
    }

    //当前位置是否合法
    private boolean pd(int[][] qp,int i,int j){
        if (i>=a+1||j>=b+1){
            return false;
        }else if (qp[i][j]!=0){
            return false;
        }
        return true;
    }
}

 

上一篇:Transformer XL源码实现


下一篇:[SHOI2014]超能粒子炮