51 lines
1.6 KiB
C++
51 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
|
||
const int N = 22;
|
||
LL f[N][N]; //递推小心爆INT，不开LL见祖宗
|
||
int ctrl[N][N]; //定义马的控制范围,一般采用int数组进行状态标识，不采用bool,因为1,0比true和false写的快
|
||
int n, m, x, y; //B点(目标点)的坐标，马的坐标
|
||
|
||
//增量数组，delta
|
||
int d[8][2] = {
|
||
{1, 2},
|
||
{1, -2},
|
||
{-1, 2},
|
||
{-1, -2},
|
||
{2, 1},
|
||
{2, -1},
|
||
{-2, 1},
|
||
{-2, -1}};
|
||
|
||
int main() {
|
||
//读入B点坐标和马的坐标
|
||
cin >> n >> m >> x >> y;
|
||
|
||
//马的实际控制范围
|
||
for (int i = 0; i < 8; i++) {
|
||
int tx = x + d[i][0], ty = y + d[i][1];
|
||
if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) ctrl[tx][ty] = 1;
|
||
}
|
||
//马所在的位置你也不能走，也踢你~
|
||
ctrl[x][y] = 1;
|
||
|
||
//如果原点在马的控制范围内，那么就是无法出发
|
||
//如果原点不在马的控制范围内，那么就是有一种方法
|
||
if (ctrl[0][0]) f[0][0] = 0;
|
||
else f[0][0] = 1;
|
||
|
||
//开始递推
|
||
for (int i = 0; i <= n; i++) //遍历整个棋盘
|
||
for (int j = 0; j <= m; j++) {
|
||
//在马的控制范围内，就放弃掉这个点，路线条数为0，默认就是0，不需要改变,直接 continue即可。
|
||
if (ctrl[i][j])continue;
|
||
//不是第0行，可以从上一行递推过来
|
||
if (i > 0) f[i][j] += f[i - 1][j];
|
||
//不是第0列，可以从上一列递推过来
|
||
if (j > 0) f[i][j] += f[i][j - 1];
|
||
}
|
||
//输出结果
|
||
cout << f[n][m];
|
||
} |