题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

6 6 3 3

输出 #1复制

6

说明/提示

对于 100%100% 的数据，1≤n,m≤201≤n,m≤20，0≤0≤ 马的坐标 ≤20≤20。

【题目来源】

NOIP 2002 普及组第四题

这里我介绍两种方法。

矩阵乘法

由于数据很小，nn 和 mm 的规模只有 2020，所以允许一些复杂度较大的做法通过。

如果我们给网格图内的点标号，记从 ii 号点到达 jj 号点的方法数为 f(i,j)f(i,j)，ii 号点到 jj 号点的边的条数为 a(i,j)(a(i,j)∈{0,1})a(i,j)(a(i,j)∈{0,1})，那么枚举经过的点 kk，则有 ii 点到 jj 点的方法数 =i=i 点到 kk 点的方法数 ×k×k 点到 jj 点的方法数，形式化的讲，f(i,j)=f(i,k)⋅a(k,j)f(i,j)=f(i,k)⋅a(k,j)。

我们惊奇的发现，这就是矩阵乘法的定义。

因此，我们连接所有互相可达的点，进行矩阵快速幂即可。

#include <bits/stdc++.h>
#define ll long long
#define rint register int
using namespace std;
int a[22][22][22][22];
ll tot[22][22][22][22];
int n,m,x,y;
int judge(int p,int q)//判断p,q是否可走
{
    if(p==x && q==y)
        return 0;
    int px=abs(p-x);
    int qy=abs(q-y);
    int mi=min(px,qy);
    int mx=max(px,qy);
    if(mi==1 && mx==2)
        return 0;
    return 1;
}
ll tmp[22][22][22][22]={0};
void ta()//将tot乘上a
{
    for(int i1=0;i1<=n;i1++)
        for(int i2=0;i2<=m;i2++)
            for(int j1=i1;j1<=n;j1++)//如果j在i号点左侧，答案必然为0
                for(int j2=i2;j2<=m;j2++)//同理
                    for(int k1=i1;k1<=j1;k1++)//k点必然在i和j之间
                        for(int k2=i2;k2<=j2;k2++)
                            tmp[i1][i2][j1][j2]+=tot[i1][i2][k1][k2]*a[k1][k2][j1][j2];
    memcpy(tot,tmp,sizeof tmp);//复制回去
}
void tt()//将tot平方
{
    for(int i1=0;i1<=n;i1++)
        for(int i2=0;i2<=m;i2++)
            for(int j1=i1;j1<=n;j1++)
                for(int j2=i2;j2<=m;j2++)
                    for(int k1=i1;k1<=j1;k1++)
                        for(int k2=i2;k2<=j2;k2++)
                            tmp[i1][i2][j1][j2]+=tot[i1][i2][k1][k2]*tot[k1][k2][j1][j2];
    memcpy(tot,tmp,sizeof tmp);
}
void pw(int ci)//求a的ci次方
{
    if(ci==0)
        return;
    pw(ci>>1);
    tt();
    if(ci&1)
        ta();
}
int main()
{
    cin>>n>>m>>x>>y;
    //连接竖向边
    for(int i=0;i<n;i++)
        for(int j=0;j<=m;j++)
            if(judge(i,j))
                a[i][j][i+1][j]=1;
    //连接横向边
    for(int i=0;i<=n;i++)
        for(int j=0;j<m;j++)
            if(judge(i,j))
                a[i][j][i][j+1]=1;
    //矩阵的单位元
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            tot[i][j][i][j]=1;
    pw(n+m);//由于要走的步数是一定的，所以就是a^(n+m)
    cout<<tot[0][0][n][m];
    return 0;
}

小学奥数

前置芝士：

1. 从 (0,0)(0,0) 走到 (m,n)(m,n) 的最短路数量=Cm+nmCm+nm​
2. 从 (0,0)(0,0) 经过 (x,y)(x,y) 到达 (m,n)(m,n) 的最短路数量=Cx+yxCm+n−x−ym−xCx+yx​Cm+n−x−ym−x​（即芝士 1 配合乘法原理的结果）

如果您了解了上面的内容，那么我们就先以样例画一张图：

0	1	2	3	4	5	6
S	.	.	.	.	.	.
.	.	x	.	x	_	.
.	x	.	.	_	x	.
.	.	.	_x	.	.	.
.	x	_	.	.	x	.
.	_	x	.	x	.	.
.	.	.	.	.	.	E

x 表示不可以走的地方。 我们分情况讨论。

1.不经过特殊格子的

我们称下划线所在的格子为特殊格子。显然这五个格子最多经过1个，所以我们只要求出总共的方法数-经过这五个格子的方法数即可求出。也就是求Cn+mn−∑i=−22Cx+yx−iCn+m−x−yn−x+iCn+mn​−∑i=−22​Cx+yx−i​Cn+m−x−yn−x+i​.

2.经过 (x−2,y+2)(x−2,y+2) 的

这种路径只有一种情况：先到达 (x−3,y+2)(x−3,y+2)，向右一格，向下一格到达 (x−2,y+3)(x−2,y+3)，然后走到 (m,n)(m,n)。

方法数为Cx+y−1x+2Cn+m−x−y−1n−x−3Cx+y−1x+2​Cn+m−x−y−1n−x−3​。

3.经过 (x+2,y−2)(x+2,y−2) 的

同理，方法数为Cx+y−1x−3Cn+m−x−y−1n−x+2Cx+y−1x−3​Cn+m−x−y−1n−x+2​。

4.经过 (x−1,y+1)(x−1,y+1) 的

要经过这个点，需要从 (x−3,y)(x−3,y) 进入马的攻击范围，右2步，下，右，下2步到达 (x,y+3)(x,y+3)，然后走到 (m,n)(m,n)。

到达 (x−3,y)(x−3,y) 的方案数为 Cx+y−3xCx+y−3x​，从 (x,y+3)(x,y+3) 到终点的方案数为 Cn+m−x−y−3n−x−3Cn+m−x−y−3n−x−3​。

5.经过 (x+1,y−1)(x+1,y−1) 的

与第 4 种情况同理，方案数为 Cx+y−3x−3Cn+m−x−y−3n−xCx+y−3x−3​Cn+m−x−y−3n−x​。

完结撒花！！！

等等，感觉有点问题...

有一种特殊情况：如果起点或终点离马的位置太近，那么上面的分类讨论的第 4 种和第 5 种情况就会出现问题——可能起点或终点本来就在马的攻击范围内。

所以，遇到这种情况别忘记特判。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll C(int m,int n)
{
    if(n<0 || m<0 || n<m)
        return 0;
    ll tot=1;
    for(int i=1;i<=m;i++)
    {
        tot*=n-i+1;
        tot/=i;
    }
    return tot;
}
int n,m,x,y;
int rt[5][5]={
0,0,1,0,0,
0,0,1,1,0,
0,0,0,1,1};//我们记录下哪些节点作为起点时，可以从右边的口子出去，其中(2,2)为马的位置
int dw[5][5]={
{},
{},
1,1,0,0,0,
0,1,1,0,0,
0,0,1,0,0};//同理，哪些可以从下边口子出去
int main()
{
    cin>>n>>m>>x>>y;
    if(n-x<3 && m-y<3)
    {
        x=n-x;
        y=m-y;
    }//为了不想把特判代码写两遍，如果终点离得太近就旋转180度，变成起点离得太近的情况
    if(x<3 && y<3)
    {
        int nx=2-x;
        int ny=2-y;//起点相对于马的坐标而言的位置
        ll tot=0;
        tot+=C(n-x,m+n-x-y-3)*rt[nx][ny];//右边出去的方法数
        tot+=C(n-x-3,m+n-x-y-3)*dw[nx][ny];//同理
        cout<<tot;
        return 0;
    }
    ll tot=C(n,n+m);
    for(int i=-2;i<=2;i++)
        tot-=C(x-i,x+y)*C(n-x+i,n+m-x-y);
    //情况1
    tot+=C(x+2,x+y-1)*C(n-x-3,n+m-x-y-1);//情况2
    tot+=C(x-3,x+y-1)*C(n-x+2,n+m-x-y-1);//情况3
    tot+=C(x,x+y-3)*C(n-x-3,n+m-x-y-3);//情况4
    tot+=C(x-3,x+y-3)*C(n-x,n+m-x-y-3);//情况5
    cout<<tot;
    return 0;
}