过河卒

题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A点 (0, 0)、B 点 (n, m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

输入输出样例

输入 #1复制

6 6 3 3

输出 #1复制

6

说明/提示

对于 $100 %$ 的数据，$1 \le n, m \le 20$，$0 \le马的坐标 \le 20$。

【题目来源】

NOIP 2002 普及组第四题

动态规划

import java.util.*;

public class Main{
        public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int bx = sc.nextInt();
        int by = sc.nextInt();

        int hx = sc.nextInt();
        int hy = sc.nextInt();

        int[][] board = new int[bx + 1][by + 1];
		// 马能走到的位置都不能再走了
        int[][] road = new int[][]{{0, 0},
                {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2},
                {1, 2}, {2, 1}, {2, -1}, {1, -2}};
		// 标记马能走到的位置
        for (int i = 0; i < 9; i++) {
            int tx = hx + road[i][0];
            int ty = hy + road[i][1];
            if (tx < 0 || ty < 0 || tx > bx || ty > by) continue;
            board[tx][ty] = 1;
        }
		// 要用long不然有些测试过不了
        long[][] dp = new long[bx + 1][by + 1];
		// 初始条件
        if (board[0][0] == 0) dp[0][0] = 1;
        for (int i = 1; i <= bx; i++) {
            if (board[i][0] != 1) {
                dp[i][0] = dp[i - 1][0];
            }
        }

        for (int j = 1; j <= by; j++) {
            if (board[0][j] != 1) {
                dp[0][j] = dp[0][j - 1];
            }
        }

        for (int i = 1; i <= bx; i++) {
            for (int j = 1; j <= by; j++) {
                if (board[i][j] == 0) {
                    // 转移方程,一个位置可以从左边或者从上边走过来
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        System.out.println(dp[bx][by]);
    }
    
}

赏

谢谢你请我吃糖果

微信