[已解决]ACM
谢谢大家！！！
[此贴子已经被作者于2006-12-2 14:49:51编辑过]
2006-11-29 23:18
2006-11-30 19:05
2006-11-30 22:06
2006-11-30 23:22
Description
如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。
棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。
Input
键盘输入B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错}
Output
屏幕输出一个整数（路径的条数）。
Sample Input
6 6 3 2
Sample Output
17
我前阵子刚做过这样一个题．
应该是ＤＰ＋组合数学+容斥原理．
先假设没有马的控制点。则题目变为求解(0,0)->(n,m)的走法个数。其实质就是求解Cm+nmin(m,n)（可用归纳法证明或直接用数学公式Csr=Cs-1r+Cs-1r-1也可证明）
再扣除其中需要经过马的控制点的走法个数，不妨设(c,d)为其中的一个控制点。再求(Cc+dmin(c,d))*(Cn+m-c-dmin(n-c,m-d))如此，依次求通过各个控制点的走法个数。
最后运用容斥原理来处理可能一躺通过多个控制点的走法个数即可。
具体实现时，用一个二维数组来实现，由于是逐步向下向右求解，整个过程正是一个ＤＰ思想的运用。
大致应该就这样，估计可能还有所疏忽...
2006-12-01 12:57
2006-12-01 16:08
2006-12-01 16:48
2006-12-01 18:26
这也是中学生信息学竞赛的题:(NOIP2002初中组)
这是pascal代码,可以当作伪代码看
{$R-,S-,I-,Q-,N+}
program c4;
const
dx: array[1 .. 8] of Shortint = (-2, -1, 1, 2, 2, 1, -1, -2);
dy: array[1 .. 8] of Shortint = (1, 2, 2, 1, -1, -2, -2, -1);
var
n, m, x, y, i, j: Byte;
g: array[0 .. 20, 0 .. 20] of Byte;
f: array[0 .. 20, 0 .. 20] of Comp;
begin
Readln(n, m, x, y);
Fillchar(g, Sizeof(g), 0);
g[x, y] := 1;
for i := 1 to 8 do
if (x + dx[i] >= 0) and (x + dx[i] <= n) and
(y + dy[i] >= 0) and (y + dy[i] <= m) then
g[x + dx[i], y + dy[i]] := 1;
f[0, 0] := 1;
for i := 1 to n do
if g[i, 0] = 0 then f[i, 0] := f[i - 1, 0];
for i := 1 to m do
if g[0, i] = 0 then f[0, i] := f[0, i - 1];
for i := 1 to n do
for j := 1 to m do
if g[i, j] = 0 then f[i, j] := f[i - 1, j] + f[i, j - 1];
Writeln(f[n, m]: 0: 0)
end.
2006-12-01 21:55
2006-12-01 23:02
