[Algorithm Elementrary]过河卒

processing

直接考虑最后一步：(i,j)这个位置只能从(i-1, j)和(i, j - 1)这两个位置来，所以定义状态f[i][j]:从A点到(i,j)坐标的路径条数，则推出状态转移方程：f[i][j] = f[i-1][j] + f[i][j-1]


NOTICE

1. points (x,y) controled by horse is 0 methods to arrive.
2. some points in margin might be controled by horse. Specially notice it.

Code

#include<iostream>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;

int n, m, x, y;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int s[1010][1010];

long long f[1010][1010];

long long calc(int i, int j){
    if(i < 0 || j < 0 || s[i][j] == 1) return 0;
    if(f[i][j] != 0) return f[i][j];
    return f[i][j] = calc(i - 1, j) + calc(i, j - 1);
} 

int main() {
    cin >> n >> m >> x >> y;
    s[x][y] = 1;
    for(int i = 0;i < 8; i ++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 0 && yy >= 0) s[xx][yy] = 1;  
    } 
    f[0][0] = 1;
    cout << calc(n, m);
    return 0;
}