P1002 [NOIP2002 普及组] 过河卒
题目
棋盘上 A A A 点有一个过河卒，需要走到目标 B B B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C C C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示， A A A 点 ( 0 , 0 ) (0,0) (0,0)、 B B B 点 ( n , m ) (n,m) (n,m)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A A A点能够到达 B B B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 B B B 点坐标和马的坐标。
输出格式
一个整数，表示所有的路径条数。
输入输出样例
输入 #1
6 6 3 3
输出 #1
6
说明/提示
对于 100 % 100\% 100%的数据， 1 ≤ n , m ≤ 20 , 0 ≤ 马的坐标 ≤ 20 1≤n,m≤20,0≤ 马的坐标 ≤20 1≤n,m≤20,0≤马的坐标≤20。
题解
以
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示到点
(
i
,
j
)
(i,j)
(i,j)处的路径方案，在没有马拦路的情况下，可以知道其路径关系为:
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
f
[
i
]
[
j
−
1
]
f[i][j]=f[i-1][j]+f[i][j-1]
f[i][j]=f[i−1][j]+f[i][j−1]
当然上式中也应当考虑边缘的特殊情况。而马所在点
(
a
,
b
)
(a,b)
(a,b)以及其跳跃一步可达地点为其控制点，则可以认为到达的地方类似于一个曼哈顿距离的正方形（除了那四个端点）：
即：
f
[
i
]
[
j
]
=
0
,
∣
i
−
a
∣
+
∣
j
−
b
∣
=
3
a
n
d
i
≠
a
,
j
≠
b
f[i][j]=0 \ , \ |i-a|+|j-b|=3\ and\ i\neq a,j\neq b
f[i][j]=0 , ∣i−a∣+∣j−b∣=3 and i=a,j=b
#include<iostream>
using namespace std;
long long n, m, a, b, f[10005][10005], block[10005][1005];
int main()
{
cin >> n >> m >> a >> b;
block[a][b] = 1;
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= m; j ++)
if(((abs(a - i) + abs(b - j) == 3) && (i != a && j != b)) || (i == a) && (j == b))
block[i][j] = 1;
f[0][0] = 1;
for(int i = 0; i <= n; i ++)
{
for(int j = 0; j <= m; j ++)
{
if(block[i][j])
f[i][j] = 0;
else
{
if(i > 0) f[i][j] += f[i - 1][j];
if(j > 0) f[i][j] += f[i][j - 1];
}
}
}
cout << f[n][m] << endl;
return 0;
}
可以边判断边移动，也可以先将判断马控制点存储后直接判断。当然，判定当前点位是否为马所控制点的方式还有：
int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
for(int i = 0; i <= 8; i ++)
block[a + fx[i]][b + fy[i]] = 1;
当然，也可即将其变为一维数组的形式：
f
[
j
]
=
f
[
j
]
+
f
[
j
−
1
]
f[j]=f[j]+f[j-1]
f[j]=f[j]+f[j−1]
其中，等式后的
f
[
j
]
f[j]
f[j]表示
f
[
i
−
1
]
[
j
]
f[i-1][j]
f[i−1][j]即为还未更新的
f
[
j
]
f[j]
f[j]，而
f
[
j
−
1
]
f[j-1]
f[j−1]为
f
[
i
]
[
j
−
1
]
f[i][j-1]
f[i][j−1]。
#include<iostream>
using namespace std;
long long n, m, a, b, f[10005], block[10005][1005];
int main()
{
cin >> n >> m >> a >> b;
n += 1; m += 1; a += 1; b += 1;
int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
for(int i = 0; i <= 8; i ++)
block[a + fx[i]][b + fy[i]] = 1;
f[1] = 1;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
if(block[i][j])
f[j] = 0;
else
f[j] += f[j - 1];
}
}
cout << f[m] << endl;
return 0;
}
此处将所有坐标平移到原点为 ( 1 , 1 ) (1,1) (1,1)处，以避免边界条件的判断。
组合数
- 倘若表格上边没有没有不可经过的点，那么从 ( 0 , 0 ) (0,0) (0,0)到 ( m , n ) (m,n) (m,n)的方案数为：
f [ m ] [ n ] = C m + n m f[m][n]=C_{m+n}^m f[m][n]=Cm+nm
- 若从
(
0
,
0
)
(0,0)
(0,0)到
(
m
,
n
)
(m,n)
(m,n)必须经过
(
x
,
y
)
(x,y)
(x,y)，则方案数为：
f [ m ] [ n ] = C m + n − x − y m − x f[m][n]=C_{m+n-x-y}^{m-x} f[m][n]=Cm+n−x−ym−x
了解到了以上的基础知识后，即可针对图中的各种特殊情况分类讨论即可。(代码就懒得敲了)