# 标数法
不知道~~小奥的~~**标数法**的看过来！
- 适用场景
类似于P1002的网格最短路径问题。
- 使用方法
如本题：
1. 先将任意的 $x$ 对应的坐标 $(x,0)$ 标为“1”，即：$f(x,0)=1.$（有马的则后面的全部标为“0”）。
2. 同理，任意的 $y$ 对应的坐标 $(0,y)$ 标为“1”，即：$f(0,y)=1.$（有马的则后面全部标为“0”）。
3. 然后，对于任意不满足1.2.的坐标，其标的数为其上方坐标标的数加左边坐标标的数。即：$f(x,y)=f(x,y-1)+f(x-1,y),x,y\ne0.$（有马的标为“0”）。
4. 路径终点坐标所标的数即为最短路径总数。如上图总数为8。
- 原理
原理其实很简单，由于只能向下或向右，所以走到 $(x,y)$ 只能由上方 $(x,y-1)$ 和左方 $(x-1,y)$ 走过去。因此就能得到：$f(x,y)=f(x-1,y)+f(x,y-1).(x,y\ne0)$
而由于马走不通，所以对于马及其能走到的位置 $(x_0,y_0)$，标的数 $f(x_0,y_0)=0.$
又因为第一行以及第一列只能向右走或向下走，所以方法数为“1”。即：$f(x,0)=f(0,y)=1.$
但如果第一行和第一列上有马，则其位置 $(x_0,0)$ 或 $(0,y_0)$ 以及后面的位置 $(0,y_0+m)$ 或 $(x_0+m,0)$ 方法数为“0”。
- 总结
没什么好总结的，但希望各位大佬帮帮我！[感激]
by Ruoyuzhou @ 2024-02-25 15:12:37
求求各位大佬！ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็！ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็！
by Ruoyuzhou @ 2024-02-25 16:29:56
判断函数一看就有问题，abs(x-x_)+abs(y-y_)用x2代表_x,用y2代替_y.如果（举例）x为3，x2也是3，y是2，y2是5按照你的条件来这样会return 1的，其实马踩不到。
@[Ruoyuzhou](/user/1287878)
by qusia_MC @ 2024-03-01 16:30:48
建议你用个数组存下马能踏足的地方
by qusia_MC @ 2024-03-01 16:47:20
@[William2019](/user/787512)
当 $x=3，y=2，x_2=3，y_2=5$ 时，
由代码**第43行**是会return 0的。
by Ruoyuzhou @ 2024-03-02 11:18:07
关于**标数法—使用方法—4**. 上图总数为**0**。
by Ruoyuzhou @ 2024-03-02 11:22:08
可是你这不对，思路没问题，听我的准没错
by qusia_MC @ 2024-03-03 19:08:15
@[William2019](/user/787512) OK.
by Ruoyuzhou @ 2024-03-03 20:49:48
我的AC代码（可以直接复制）
```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x1,y1,x2,y2;//(x1,y1)为棋盘，(x2,y2)为马。
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
long long m[x1+1][y1+1];//构建棋盘
bool a[x1+1][y1+1];
a[x2][y2]=1;
if(x2-1>=0&&y2-2>=0)a[x2-1][y2-2]=1;
if(x2-2>=0&&y2-1>=0)a[x2-2][y2-1]=1;
if(x2+1<=x1&&y2+2<=y1)a[x2+1][y2+2]=1;
if(x2+2<=x1&&y2+1<=y1)a[x2+2][y2+1]=1;
if(x2-1>=0&&y2+2<=y1)a[x2-1][y2+2]=1;
if(x2-2>=0&&y2+1<=y1)a[x2-2][y2+1]=1;
if(x2+1<=x1&&y2-2>=0)a[x2+1][y2-2]=1;
if(x2+2<=x1&&y2-1>=0)a[x2+2][y2-1]=1;
for(int i=0;i<=y1;i++)
{
if(a[0][i])
{
break;
}
m[0][i]=1;
}
for(int i=0;i<=x1;i++)
{
if(a[i][0])
{
break;
}
m[i][0]=1;
}//将第一行和第一列赋值为"1"
for(int i=1;i<=y1;i++)
{
for(int j=1;j<=x1;j++)
{
if(!a[j][i])
{
if(!a[j][i-1])m[j][i]+=m[j][i-1];//标数法
if(!a[j-1][i])m[j][i]+=m[j-1][i];
}
//若为马及其能到的地方方法数为"0"
}
}
cout<<m[x1][y1];//输出终点方法数
return 0;
}
```
@[Ruoyuzhou](/user/1287878)
by qusia_MC @ 2024-03-04 15:48:35
@[William2019](/user/787512) 栓Q
by Ruoyuzhou @ 2024-03-05 18:59:08