首页 > 试题广场 >

[NOIP2002 普及组] 过河卒

[编程题][NOIP2002 普及组] 过河卒
  • 热度指数：4411 时间限制：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)的关系是 


数据范围： ，马的坐标 


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


输出描述:
输出路径总数
示例1

输入

6 6 3 3

输出

6
示例2

输入

5 4 2 3

输出

3
示例3

输入

2 5 3 5

输出

1
算法知识视频讲解
添加回答
C++
rairy8头像 rairy8 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m,x,y;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    long dp[m+2];
    memset(dp,0,sizeof(dp));
    dp[1]=1;//初始步1 保证dp[0]始终为0 限制边界
    for(int i=0;i<=n;++i){
        for(int j=1;j<=m+1;++j){
            if(abs(i-x)<=2 && abs(j-1-y)<=2 && (abs(i-x)+abs(j-1-y))==3 || (i==x && j==y+1)) dp[j]=0; //保证马位置以及周围步数为0；
            else dp[j]=dp[j-1]+dp[j];
        }
    }
    printf("%ld",dp[m+1]);
}

发表于 2023-01-11 19:37:29 回复(0)
C++
Spectre_头像 Spectre_ 
#include <iostream>
using namespace std;

bool check(int x1, int y1, int x, int y) {
    if ((x1 == x && y1 == y) || 
        (x1 != x && y1 != y && abs(x1 - x) + abs(y1 - y) == 3)) return false;
    return true;
}

long process(int n, int m, int x, int y) {
    // 时间复杂度O(MN)，空间复杂度O(MN)
    long dp[n + 1][m + 1];  // 有超过int32的答案，使用long
    if (!check(0, 0, x, y)) return 0;  // (0,0)在马的控制点上，直接return 0
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) dp[i][0] = check(i, 0, x, y) ? dp[i - 1][0] : 0;
    for (int j = 1; j <= m; ++j) dp[0][j] = check(0, j, x, y) ? dp[0][j - 1] : 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = check(i, j, x, y) ? dp[i - 1][j] + dp[i][j - 1] : 0;
        }
    }
    return dp[n][m];
}

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    cout << process(n, m, x, y);
    return 0;
}

发表于 2022-11-01 11:21:23 回复(0)
呼延棋大宝头像 呼延棋大宝 
n , m , x , y = map(int,input().split())

dp = [[0 for _ in range(max(m,y)+1)]for _ in range(max(n,x)+1)]
horpos = [[0 for _ in range(max(m,y)+1)]for _ in range(max(n,x)+1)]

for i in range(len(horpos)):
    for j in range(len(horpos[0])):
        if i == x and j == y:
            horpos[i][j] = 1
        if abs(i-x) + abs(j-y) == 3 and i != x and j != y:
            horpos[i][j] = 1

for i in range(len(dp)):
    for j in range(len(dp[0])):
        if horpos[i][j] == 1:
            dp[i][j] = 0
        else:
            dp[0][0] = 1
            if i == 0 and j != 0:
                dp[i][j] = dp[i][j-1]
            elif j == 0 and i != 0:
                dp[i][j] = dp[i-1][j]
            elif j != 0 and i != 0:
                dp[i][j] = dp[i][j-1] + dp[i-1][j]

print(dp[n][m])

发表于 2023-04-22 16:35:41 回复(0)
C/C++
牛客309028246号头像 牛客309028246号 
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
using namespace std;

inline bool inPoint(int i, int j, int x, int y) {
    // 不能吃马, 同时判断马的位置
    if (i == x && j == y) return true;
    if (abs(i - x) + abs(j - y) == 3 && i != x && j != y) {
        return true;
    }
    return false;
}

signed main() {
    int m, n, x, y;
    while (cin >> m >> n >> x >> y) {
        vector<vector<int>> f(m+1, vector<int>(n+1));
        f[0][0] = 1;
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (inPoint(i, j, x, y))
                    f[i][j] = 0;
                else {
                    int up = i == 0 ? 0 : f[i - 1][j];
                    int left = j == 0 ? 0 : f[i][j - 1];
                    f[i][j] += left + up;
                }
            }
        }
        cout << f[m][n] << endl;
    };
}


发表于 2023-03-27 14:44:11 回复(0)
C++
牛客288355985号头像 牛客288355985号 
#include<iostream>
#include<algorithm>
#include<cmath>
using lli = long long int;
using namespace std;

// dp[i][j]=dp[i][j-1]+dp[i-1][j]
// dp[-1][]=0
// dp[][-1]=0
// dp[0][0]=1
// dp[i][j]=0  if |i-x|+|j-y|==0 and i!=x and j!=y
// dp[i][j]=0  if i==x and j==y

int x,y;
lli dp(int i,int j){
  if(i<0||j<0) return 0;
  static lli cache[29][29];
  if(cache[i][j]!=0) return cache[i][j];
  if(i==0&&j==0) return cache[i][j]=1;
  if(abs(i-x)+abs(j-y)==3 && i!=x && j!=y) return cache[i][j]=0;
  if(i==x&&j==y) return cache[i][j]=0;
  return cache[i][j]=dp(i,j-1)+dp(i-1,j);
}

int main(){
  int n,m;
  cin>>n>>m>>x>>y;
  cout<<dp(n,m)<<endl;
}

发表于 2022-08-28 12:26:15 回复(0)
Python 3
Kiron_L头像 Kiron_L 
def check(x, y, i, j):
    # 排除马的位置
    return (abs(i - x) + abs(j - y) == 3 and i != x and j != y)&nbs***bsp;(i == x and j == y)


def solution(n, m, x, y):
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    dp[0][0] = 1
    for j in range(1, m + 1):  # 第一行
        dp[0][j] = 0 if check(x, y, 0, j) else dp[0][j - 1]
    for i in range(1, n + 1):  # 第一列
        dp[i][0] = 0 if check(x, y, i, 0) else dp[i - 1][0]
    for i in range(1, n + 1):  # 动态转移
        for j in range(1, m + 1):
            dp[i][j] = 0 if check(x, y, i, j) else dp[i - 1][j] + dp[i][j - 1]
    return dp[n][m]


n, m, x, y = map(int, input().split())
print(solution(n, m, x, y))

发表于 2022-08-17 22:41:53 回复(1)
C++
zhengluoqi头像 zhengluoqi 
#include<iostream>
#include<cstring>
using namespace std;
int main(){
    long long dp[25][25];
    memset(dp,-1,sizeof(dp));
    int x,y,n,m;
    cin>>n>>m>>x>>y;
    x+=2;y+=2;n+=2;m+=2;
    dp[x][y]=dp[x-2][y-1]=dp[x-1][y-2]=dp[x-2][y+1]=dp[x+1][y-2]
        =dp[x+2][y-1]=dp[x-1][y+2]=dp[x+1][y+2]=dp[x+2][y+1]=0;
    for(int i=3;i<=n;i++)dp[i][1]=0;
    for(int j=2;j<=m;j++)dp[1][j]=0;
    dp[2][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(dp[i][j]!=0)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    cout<<dp[n][m];
	return 0;
}

发表于 2022-08-17 21:29:43 回复(0)
Java
hh求offer头像 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.头像 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)
Python 3
勤劳的大西瓜要暴富头像 勤劳的大西瓜要暴富
#二维数组 动态规划
#卒只能向右或向下走。所以状态方程：dp[i][j]=dp[i−1][j]+dp[i][j−1]。
#注意如果该点是马点或者马可以跳到的点 则该点到不了 dp[i][j]应该设置为0
#判断该点是不是可行点 即是否为对方马的控制点 
def panduan(i,j,x,y):
    if (abs(i-x)+abs(j-y)==3 and i!=x and j!=y)&nbs***bsp;(i==x and j==y):
        return True
    else:
        return False
#
if __name__ == '__main__':
    n, m, x, y = map(int,input().split())
    dp=[[1 for j in range(m+1)] for i in range(n+1)]#细节 数组的size: n+1*m+1
    for j in range(1,m+1):#初始化第一行 
        dp[0][j]=0 if panduan(0,j,x,y) else dp[0][j-1]         
    for i in range(1,n+1):#初始化第一列
        dp[i][0]=0 if panduan(i,0,x,y) else dp[i-1][0]
    for i in range(1,n+1):
        for j in range(1,m+1):
            dp[i][j]=0 if panduan(i,j,x,y) else dp[i-1][j]+dp[i][j-1]#注意限制条件的把握
    print(dp[-1][-1])


发表于 2022-04-17 21:25:21 回复(0)
C++
元气少女李逵头像 元气少女李逵 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    vector<vector<long > > dp(n+1,vector<long>(m+1,1));
    if(x-2>=0 && x-2<=n && y-1>=0 && y-1<=m)
    {
       dp[x-2][y-1]=0;
    }
    if(x-2>=0 && x-2<=n && y+1>=0 && y+1<=m)
    {
       dp[x-2][y+1]=0;
    }
    if(x-1>=0 && x-1<=n && y-2>=0 && y-2<=m)
    {
       dp[x-1][y-2]=0;
    }
    if(x-1>=0 && x-1<=n && y+2>=0 && y+2<=m)
    {
       dp[x-1][y+2]=0;
    }
    if(x+2>=0 && x+2<=n && y-1>=0 && y-1<=m)
    {
       dp[x+2][y-1]=0;
    }
    if(x+1>=0 && x+1<=n && y-2>=0 && y-2<=m)
    {
       dp[x+1][y-2]=0;
    }
    if(x+2>=0 && x+2<=n && y+1>=0 && y+1<=m)
    {
       dp[x+2][y+1]=0;
    }
    if(x+1>=0 && x+1<=n && y+2>=0 && y+2<=m)
    {
       dp[x+1][y+2]=0;
    }
    if(x>=0 && x<=n && y>=0 && y<=m)
    {
       dp[x][y]=0;
    }
    
    
    for(int i=1;i<=m;i++)
    {
        if(dp[0][i]!=0)
        {
            dp[0][i]=dp[0][i-1];
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        if(dp[i][0]!=0)
        {
            dp[i][0]=dp[i-1][0];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((x==2 && y==1) || (x==1 && y==2))
            {
                cout<<"0"<<endl;
                return 0;
            }
            else
            {
                if(dp[i][j]!=0)
                {                    
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];                    
                }
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}
                            

发表于 2022-04-09 22:21:02 回复(0)
Java
刻苦的小章鱼不想上班头像 刻苦的小章鱼不想上班
为什么1000 1 1000 1000的结果不正确？
发表于 2022-03-11 14:26:15 回复(1)
提交观点

问题信息

动态规划
难度：
13条回答 990浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号