[NOIP2002 普及组] 过河卒

[编程题][NOIP2002 普及组] 过河卒

热度指数：4429 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 $|x1-x|+|y1-y|=3 ，且x1 \neq x ,y1\neq y \$

数据范围： $1 \le n,m \le 20\$ ，马的坐标 $0 \le x,y \le 20 \$

$1 \le a,b,c,d \le 1000 \$

输入描述:

仅一行，输入 n,m,x,y 四个正整数。分别表示B点坐标和马的坐标

输出描述:

输出路径总数

示例1

输入

6 6 3 3

输出

示例2

输入

5 4 2 3

输出

示例3

输入

2 5 3 5

输出

算法知识视频讲解

Java

hh求offer

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] split = scanner.nextLine().split(" +");
        int n = Integer.parseInt(split[0]);
        int m = Integer.parseInt(split[1]);
        int x = Integer.parseInt(split[2]);
        int y = Integer.parseInt(split[3]);
         long[][] dp = new long[n+1][m+1];
        if(x == 0 && y == 0){
            System.out.println(0);
            return;
        }
        dp[0][0] = 1;
        //初始化第一列
        for (int i = 1; i <= n; i++) {
            if(!check(x,y,i,0)){
                dp[i][0] = dp[i-1][0];
            }else{
                dp[i][0] = 0;
            }
        }
        //初始化第一行
        for (int j = 1; j <= m; j++) {
            if(!check(x,y,0,j)){
                dp[0][j] = dp[0][j-1];
            }else{
                dp[0][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(!check(x,y,i,j)){
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        System.out.println(dp[n][m]);
    }
    public static boolean check(int x, int y, int i, int j){
        if(i == x && j == y){
            return true;
        }
        int tmp1 = Math.abs(i - x);
        int tmp2 = Math.abs(j - y);
        if(tmp1 + tmp2 == 3 && x != i && y != j){
            return true;
        }
        return false;
    }
}

发表于 2022-05-04 11:12:02 回复(0)

Java

ByteWong.

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt() + 1;
            int m = in.nextInt() + 1;
            int x = in.nextInt() + 1;
            int y = in.nextInt() + 1;

            long[][] dp = new long[n+1][m+1];
            dp[1][1] = 1;
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=m;j++) {
                    if(i == x-1 && j== y-2 || i == x-2 && j == y-1 || i == x-2 && j == y+1
                            ||  i == x-1 && j == y+2 || i== x+1 && j==y+2 || i==x+2 && j== y+1 || i == x+2 && j == y-1
                            || i == x+1 && j == y-2 || i == x &&  j == y) {
                        dp[i][j] = -1;
                    }
                }
            }

            for(int i=2;i<=n;i++) {
                if(dp[i-1][1] == -1){
                    dp[i][1] = -1;
                } else if(dp[i][1] != -1){
                    dp[i][1] = dp[i-1][1];
                } else {
                    dp[i][1] = -1;
                }
            }
            
            for(int j=2;j<=m;j++) {
                if(dp[1][j-1] == -1){
                    dp[1][j] = -1;
                } else if(dp[1][j] != -1) {
                    dp[1][j] = dp[1][j-1];
                } else {
                    dp[1][j] = -1;
                }
            }

            for(int i=2;i<=n;i++) {
                for(int j=2;j<=m;j++) {
                    if(dp[i][j] == -1){
                        continue;
                    }

                    if(dp[i-1][j] == -1 && dp[i][j-1] == -1) {
                        dp[i][j] = -1;
                    }

                    if(dp[i-1][j] != -1) {
                        dp[i][j] += dp[i-1][j];
                    }

                    if(dp[i][j-1] != -1) {
                        dp[i][j] += dp[i][j-1];
                    }
                }
            }
            System.out.print(dp[n][m]);
        }
    }
}

发表于 2022-04-26 00:20:05 回复(0)

Java

辣鸡别卷了

dp要用long数组

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int x=scanner.nextInt();
        int y=scanner.nextInt();
        HorseFoot horseFoot= new HorseFoot(new Coordinate(x, y));
        long[][] dp=new long[n+1][m+1];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(i==0&&j==0){
                    dp[i][j]=1;
                    continue;
                }
                long top=0,left=0;
                if(i>0){
                    top=horseFoot.onFoot(new Coordinate(i-1,j))?0:dp[i-1][j];
                }
                if(j>0){
                    left=horseFoot.onFoot(new Coordinate(i,j-1))?0:dp[i][j-1];
                }

                dp[i][j]=left+top;
            }
        }
        System.out.println(dp[n][m]);
    }
    static class HorseFoot{
        ArrayList<Coordinate> list=new ArrayList<>(9);
        Coordinate horse;
        HorseFoot(Coordinate horse){
            this.horse=horse;
            list.add(horse);
            list.add(new Coordinate(horse.x + 1, horse.y + 2));
            list.add(new Coordinate(horse.x + 1, horse.y - 2));
            list.add(new Coordinate(horse.x - 1, horse.y + 2));
            list.add(new Coordinate(horse.x - 1, horse.y - 2));
            list.add(new Coordinate(horse.x + 2, horse.y + 1));
            list.add(new Coordinate(horse.x + 2, horse.y - 1));
            list.add(new Coordinate(horse.x - 2, horse.y + 1));
            list.add(new Coordinate(horse.x - 2, horse.y - 1));
        }
        public boolean onFoot(Coordinate c){
            return list.contains(c);
        }
    }
    static class Coordinate{
        int x;
        int y;
        Coordinate(int x,int y){
            this.x=x;
            this.y=y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Coordinate)) return false;

            Coordinate that = (Coordinate) o;

            if (x != that.x) return false;
            return y == that.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }
}

发表于 2022-04-21 19:53:42 回复(1)

Java