题解 P1002 【过河卒】

2019 年 07 月 21 日

1136 次浏览

826字数

蒟蒻做这道题有一些简单的想法。
------------------------------

仔细思索了一下，感觉跟小学奥数的感觉很像
举个例子
![](https://hibanaw.icu/usr/uploads/2021/02/1122432131.png)
可以这么解
作图，其中绿色为A，橘色为B，红色为断路C，每隔数字表示到达该位置的道路的条数（格子对应原图的格点）
到达图中(1,1)的路是到达(0,1)和(1,0)位置的总和，
(4,2)的左边因为是断路所以只可以由(4,1)一条路到达，可以将断路视为0
![](https://hibanaw.icu/usr/uploads/2021/02/3722531786.png)
于是这道题的基本思路就有了
建立如上的一个棋盘，将马控制点全部扣去，再进行加法
为方便进行运算（toulan），我决定将棋盘向两个正方向分别挪一格
注意，题目提示表示至少要用long long。
我的代码如下

```cpp
#include<bits/stdc++.h> //万能头文件

using namespace std;

int main()
{
    long long board[101][101], cn, cm, n, m; //其中cn和cm表示C的坐标
    memset(board, -1, sizeof(board)); //将整个棋盘赋值为-1，表示空地，可以落子
    cin >> n >> m >> cn >> cm;
    int t[8] = {1,-1,1,-1,2,-2,-2,2};
    int i = 0, j = 0;
    cn +=1; //因为将整个棋盘挪了一格，所以
    cm +=1;
    board[cn][cm] = 0; //马所在的点也是控制点
    for(i = 0; i <= 7; i++)
        board[cn+t[i]][cm+t[7-i]] = 0; //一个比较好的跳马问题快速解决办法
    for(i = 0; i <= n + 1; i++)
        board[i][0] = 0; //最下面和最左面两条不可以下子
    for(i = 0; i <= m + 1; i++)
        board[0][i] = 0;
    board[1][1] = 1; //为起点赋值，起点出发有且只有一种情况
    for(i = 1; i <= n + 1; i++)
        for(j = 1; j <= m + 1; j++)
        {
            if(board[i][j] == -1) //如果可以下子，则
                board[i][j] = board[i-1][j] + board[i][j-1];
        }
    cout << board[n+1][m+1];
    return 0;
}
```

希望大家可以给我的题解提提意见，谢谢！