过河卒

过河卒

题意：

对于n * m的棋盘，棋盘中有九个点不能走，问你一个大头兵从左上角走到右下角的路径有多少条

思路：

使出秘技dp

状态转移方程是：tr[i] [j] = tr[i - 1] [j] + tr[i] [j - 1]

有一些细节：

• 🐎走的八个点的坐标得找对，同时得判这八个点是否符合题意
• 别忘记马初试点也不可以走
• 边界位置i = 1或 j = 1的时候，状态转移方程得变，因为此时只有一条路
• 开long long！（不开longlong见祖宗！！！！！）

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 7
#define endl '\n'
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
        ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, m, x, y, xx, yy;
ll tr[25][25];
int dx[] = {2,1,-1,-2,-2,-1,1,2};//马走的八个方向
int dy[] = {1,2,2,1,-1,-2,-2,-1};

bool judge(ll x, ll y){//判断八个点是否符合题意
    if(x > n || x < 0 || y < 0 || y > m)return false;
    else return true;
}

int main(){
    cin>>n>>m>>x>>y;
    memset(tr, -1, sizeof(tr));//给数组赋值为-1，为的是与那九个点区分开
    for(int i = 0; i < 8; ++i){
        xx = x + dx[i];yy = y + dy[i];
        if(judge(xx, yy)){
            tr[xx][yy] = 0;//九个点赋值为0
        }
    }
    tr[x][y] = 0;//别忘了这个点
    for(int i = 0; i <= n; ++i)
    for(int j = 0; j <= m; ++j){
        if(tr[i][j] == -1){//不是马
            if(i - 1 >= 0 && j - 1 >= 0){//非第一行或第一列
                tr[i][j] = tr[i - 1][j] + tr[i][j - 1];
            }
            else if(i - 1 >= 0 && j - 1 < 0){//第一列
                tr[i][j] = tr[i - 1][j];
            }
            else if(i - 1 < 0 && j - 1 >= 0){//第一行
                tr[i][j] = tr[i][j - 1];
            }
            else tr[i][j] = 1;//0，0的点
        }
    }
    cout<<tr[n][m]<<endl;
    return 0;
}