[NOIP2002]过河卒 标准递归

 题目地址

登录—专业IT笔试面试备考平台_牛客网

输入输出描述

如果没有马存在 就是一个经典的递归题

// Dduo
// Bhu Bigdata 1421
package Dduo;
import java.util.*;
// Eslipse IDE 2020-08
// JDK 1.8
// 2024/5/21

public class Main  {
    static Scanner sc=new Scanner(System.in);
    static int cnt=0;
    public static void main(String[] args) {
    	//过河卒
    	//b
    	int n=sc.nextInt();
    	int m=sc.nextInt();
    	//马
//    	int x=sc.nextInt();
//    	int y=sc.nextInt();
    	//递归
    	rec(n,m);
    	
    	System.out.print(cnt);
    }
    public static void rec(int x, int y) {
    	//递归出口
    	if(x<0||y<0)return;
    	//递归式
    	else {
    		if(x==0&&y==0)cnt++;
    		else {
    			rec(x-1,y);
    			rec(x,y-1);
    		}
    	}
    }
 }

递归解法

// Dduo
// Bhu Bigdata 1421
package Dduo;
import java.util.*;
// Eslipse IDE 2020-08
// JDK 1.8
// 2024/5/21

public class Main  {
    static Scanner sc=new Scanner(System.in);
    //计数器
    static int cnt=0;
    //马
    static int horse_X,horse_Y;
    static int x1,y1;
    static int x2,y2;
    static int x3,y3;
    static int x4,y4;
    static int x5,y5;
    static int x6,y6;
    static int x7,y7;
    static int x8,y8;
    public static void main(String[] args) {
    	//过河卒
    	//b
    	int n=sc.nextInt();
    	int m=sc.nextInt();
    	//马
    	horse_X=sc.nextInt();
    	horse_Y=sc.nextInt();
    	
    	x1=horse_X+1;y1=horse_Y-2;
    	x2=horse_X+2;y2=horse_Y-1;
    	x3=horse_X+2;y3=horse_Y+1;
    	x4=horse_X+1;y4=horse_Y+2;
    	x5=horse_X-1;y5=horse_Y+2;
    	x6=horse_X-2;y6=horse_Y+1;
    	x7=horse_X-2;y7=horse_Y-1;
    	x8=horse_X-1;y8=horse_Y-2;
    	
    	//递归
    	rec(n,m);
    	
    	System.out.print(cnt);
    }
    public static void rec(int x, int y) {
    	//递归出口
    	//跑出棋盘
    	if(x<0||y<0)return;
    	//马的控制范围
    	if(x==horse_X&&y==horse_Y)return;
    	if(x==x1&&y==y1)return;
    	if(x==x2&&y==y2)return;
    	if(x==x3&&y==y3)return;
    	if(x==x4&&y==y4)return;
    	if(x==x5&&y==y5)return;
    	if(x==x6&&y==y6)return;
    	if(x==x7&&y==y7)return;
    	if(x==x8&&y==y8)return;
    	//递归式
    	if(x==0&&y==0)cnt++;
    		else {
    			rec(x-1,y);
    			rec(x,y-1);
    		}
    	}
 }