题解 | #过河卒#

注意开long long !!!
题目考点：dp
题目大意：从起点到终点的路径数（多啰嗦一句，分析是dp还是bfs的点就是看求的是最短路径还是路径条数，两种算法解决的问题不同）
题目分析：dp[ i ] [ j ] 表示走到（i,j）的路径数，正常情况下dp[i][j]等于上面走下来和左边走过来的路径条数相加，即dp[ i ] [ j ] = dp[ i - 1 ] [ j ] + dp[ i ] [ j - 1 ]
遇到马控制的点特判即可

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 25;
LL  dp[N][N];
int dir[8][2] = {{-1, -2},{-2, -1},{-2, 1},{-1, 2},{1, 2},{2, 1},{2, -1},{1, -2}};

int main()
{
    int n, m, a, b;
    int x, y;
    scanf("%d%d%d%d", &n, &m, &a, &b);
    a += 1, b += 1, n += 1, m += 1;

    dp[1][1] = 1;  //起点
    dp[a][b] = -1; //马所在点

    for(int i = 0; i < 8; i++) //马控制点
    {
        x = a + dir[i][0];
        y = b + dir[i][1];
        if(x > 0 && y > 0)
            dp[x][y] = -1;
    }

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        if(dp[i][j] != -1)
        {
            if(dp[i-1][j] != -1)dp[i][j] += dp[i-1][j];
            if(dp[i][j-1] != -1)dp[i][j] += dp[i][j-1];
        }
    }

    printf("%lld", dp[n][m]);
    return 0;
}