审题本题需要我们在避开马的守护范围的情况下找到所有可以从左上角起点走到右下角终点的方案思路方法一动态规划1状态表示f[i][j]表示从起点走到(i,j)点的所有路径方案数2状态转移方程由于行走规则是向右和向下走所以在最后一步中可以走到目标位置的只有其上方和左边的节点对于可以到达的节点对于无法到达的位置需要注意的是本题中无法到达马本身和其守护的位置而我们可以发现马的守护范围是有规律的守护节点距离马的曼哈顿距离都是3曼哈顿距离等于三就是只需要走三步就可以到达当前节点但是本题中还有四个节点虽然和马的曼哈顿距离是3,却不是马的守护范围他们就是满足ix或jy的节点。然后还有个节点就是马本身了3初始化由于本题是从0,0开始走的如果我们直接填表会导致越界访问。所以我们可以让整个表向右下角移动一位从而让表的起点为1,1然后再在f[0][1]/f[1][0]中选择任一填写为1即可4填表顺序从上到下从左到右根据行走规则得到的状态转移方程表明我们想填写该节点的前提是填写完该节点的上一位节点和左一位节点所以我们需要从上到下从左到右填表5输出答案直接输出f[n][m]虽然我们整个表移动过但是这并不影响最终答案最终答案就是表的有效范围的最右下角解题#includeiostream #includealgorithm using namespace std; typedef long long ll; const int N 30; int n, m,x,y; ll f[N][N]; int main() { cin n m x y; n; m; x; y;//集体右下角移动 //初始化 f[0][1] 1; //填表 for (int i 1; i n; i) { for (int j 1; j m; j) { if ((i ! x j ! y (abs(i - x) abs(j - y)) 3) || (i x j y)) { f[i][j] 0; } else { f[i][j] f[i][j - 1] f[i - 1][j]; } } } cout f[n][m] endl; return 0; }注意计算结果的数量是很大的极有可能超过了int数据范围所以我们应该使用longlong数据类型来存储f数组的答案P1002 [NOIP 2002 普及组] 过河卒 - 洛谷
