1224 - 过河卒

本文主要是介绍1224 - 过河卒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

AA 点有一个过河卒，需要走到目标 BB 点。

卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图的 CC 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

例如：下图 CC 点可以控制 99 个点（图中的 P1,P2 \dots P8P1,P2…P8 和 CC ），卒不能通过对方马的控制点。 棋盘用坐标表示，现给定 AA 点位置为 (0,0)(0,0)， BB 点位置为 (n,m)(n,m) (n,mn,m 为不超过 1010 的整数)，马的位置 CC 为 (X,Y)(X,Y)（约定: CC 点与 AA 点不重叠，与 BB 点也不重叠）。

要求你计算出卒从 AA 点能够到达 BB 点的路径的条数。

输入

BB 点的坐标 (n,m)(n,m) 以及对方马的坐标 (X,Y)(X,Y)；（马的坐标一定在棋盘范围内，但要注意，可能落在边界的轴上）

输出

输出卒从 AA 点能够到达 BB 点的路径条数。

样例

输入

6 6 3 2

输出

17

来源

递推

#include<bits/stdc++.h>
using namespace std;
int a[25][25];
int main(){int n,m,x,y;cin>>n>>m>>x>>y;for(int i=0;i<=n;i++)for(int j = 0;j<=m;j++)a[i][j] = -1;int dx[10]={0,-1,-1,-2,-2,1,1,2,2};int dy[10]={0,-2,2,-1,1,-2,2,-1,1};for(int i=0;i<=9;i++){int ix=dx[i]+x,iy=dy[i]+y;if(ix>=0&&ix<=n&&iy>=0&&iy<=m)a[ix][iy] = 0;}a[0][0]=1;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){if(i==0&&a[i][j]==-1)a[i][j]=a[i][j-1];else if(j==0&&a[i][j]==-1)a[i][j]=a[i-1][j];else if(a[i][j]==-1)a[i][j]=a[i][j-1]+a[i-1][j];}}cout<<a[n][m];return 0;
}

这篇关于1224 - 过河卒的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---