洛谷 P1002 過河卒（rush B）

原題連結

對于任意一個可以行走的格子，路徑條數 = 上面的格子路徑條數+左邊的條數

（因為rush B不能走回頭路，隻能往下、右，是以任意的格子的前一個格子，隻能是上面或左邊，加起來就是可以用于rush的路徑數量）

特殊處理一下，馬狙盯住的位置不能rush

還有的就是要注意 int 裝不下結果，要用 long long

rush B代碼

時 間 複 雜 度 O ( n 2 ) 時間複雜度O(n^2) 時間複雜度O(n2)

//#define local 1

#include<cstdio>
long long map[30][30];
int b_x, b_y;//b點坐标
int ho_x, ho_y;//馬的坐标 horse

inline long long ReLU(long long n){
	if (n <= 0)
		return 0;
	return n;
}

void rush_B(){
	map[0][0] = 1;//恐怖分子開局肯定在匪家
	//一定要rush B點，不對方向的全槍斃
	for (int i = 0; i <= b_x; i++)
		for (int j = 0; j <= b_y; j++){
			//不要送人頭給馬狙
			if (map[i][j] == -1)
				continue;
			//不能穿模，i=0或j=0容易穿模，處理一下
			if (i - 1 >= 0){
				map[i][j] += ReLU(map[i-1][j]);
			}
			if (j - 1 >= 0){
				map[i][j] += ReLU(map[i][j - 1]);
			}
		}
}

void unreachable_marking(){
	//标記馬狙盯的位置，即匪rush不了的路
	map[ho_x][ho_y] = -1;
	int place[] = { 2, 1 };
	int sign[] = { 1, -1 };
	for (int i = 0; i < 2; i++){
		for (int n = 0; n < 2; n++)
			for (int m = 0; m < 2; m++){
				int x = ho_x + place[i] * sign[n];
				int y = ho_y + place[!i] * sign[m];
				if (x >= 0 && y >= 0)
					map[x][y] = -1;
			}
	}
}

int main(){
#ifdef local
	freopen("in.txt","r",stdin);
#endif
	
	scanf("%d%d%d%d", &b_x, &b_y, &ho_x, &ho_y);
	unreachable_marking();
	
	rush_B();
	printf("%lld\n",map[b_x][b_y]);
	return 0; 
}