题目描述
棋盘上 \(A\) 点有一个过河卒，需要走到目标 \(B\) 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 \(C\) 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，\(A\) 点 \((0, 0)\)、\(B\) 点 \((n, m)\)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 \(A\) 点能够到达 \(B\) 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 \(B\) 点坐标和马的坐标。
输出格式
一个整数，表示所有的路径条数。
样例 #1
样例输入 #1
6 6 3 3
样例输出 #1
6
提示
对于 \(100 \%\) 的数据，\(1 \le n, m \le 20\)，\(0 \le\) 马的坐标 \(\le 20\)。
【题目来源】
NOIP 2002 普及组第四题
点击查看代码
import java.util.Scanner;
public class Main {
static long s =0; //保存可行情况
static int a[][];
private static void dfs(int x, int y, int[][] a) {
if(x<0||x>a.length-1||y<0||y>a[0].length-1) //判断该点是否超界
return;
if(a[x][y]==1) //判断该点是否为马的控制点
return;
if(x==a.length-1&&y==a[0].length-1) { //是否到达B点
s++;
return;
}
dfs(x+1, y, a); //向下走
dfs(x, y+1, a); //向右走
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//马的控制点的8个方向
int b[][] = { { -2, -1 }, { -1, -2 }, { 1, -2 }, { 2, -1 }, { 2, 1 }, { 1, 2 }, { -1, 2 }, { -2, 1 } };
int n = scanner.nextInt()+1;
int m = scanner.nextInt()+1;
int x = scanner.nextInt();
int y = scanner.nextInt();
a = new int[n][m];
a[x][y] = 1;
//找出马的控制点，置a[x][y] = 1
for (int i = 0; i < 8; i++) {
int d1 = b[i][0] + x;
int d2 = b[i][1] + y;
if (d1 < 0 || d1 >= m || d2 < 0 || y >= n)
continue;
a[d1][d2] = 1;
}
dfs(0, 0, a);
System.out.println(s);
}
}