NC16708 过河卒_牛客博客

链接：https://ac.nowcoder.com/acm/problem/16708
来源：牛客网

题目描述

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。

棋盘用坐标表示，A 点（0,0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入描述:

输入B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错}

输出描述:

输出一个整数（路径的条数）。

思路

首先这道题很容易求出转移方程，

但是是用 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$ 好

还是 $dp[i+1][j]+=dp[i][j],dp[i][j+1]+=dp[i][j]$ ，

其实各有各的好处，但是我选择了后者。

在转移的过程中容易出现的错误是@savage指出的：

我做题时候直接将所有的马能到达的和马自己赋值为-1，然后加判断去遍历所有位置

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;

ll dp[100][100];
int dir[10][2] = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
int main() {
//    open;close;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    dp[x2][y2]=-1;
    for(int i=0;i<8;++i){
        int xx=x2+dir[i][0],yy=y2+dir[i][1];
        if(xx<0||yy<0||xx>x1||yy>y1)continue;
        dp[xx][yy]=-1;
    }
    dp[0][0] = 1;
    for(int i = 0; i <= x1; ++i) {
        for(int j = 0; j <= y1; ++j) {
            if(dp[i][j] != -1) {
                if(dp[i + 1][j] != -1)
                    dp[i + 1][j] += dp[i][j];
                if(dp[i][j + 1] != -1)
                    dp[i][j + 1] += dp[i][j];
            }
        }
    }
    cout<<dp[x1][y1]<<endl;


}