80pts紧急求助SOS
查看原帖
80pts紧急求助SOS
1097177
longhaoyuan楼主2024/5/30 20:47

本蒟蒻轻敌,拿了个80分,dalao们救命!QwQ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 25;

ll n, m, hx, hy;
ll dp[maxn][maxn];
set<pair<ll, ll>> forbidden; 

int main(){
	scanf("%lld %lld %lld %lld", &n, &m, &hx, &hy);
	forbidden.emplace(hx, hy);
	for (ll i = -2LL; i <= 2LL; i++){
		if (!i) continue;
		for (ll j = -2LL; j <= 2LL; j++){
			if (!j) continue;
			if (abs(i) + abs(j) != 3) continue;
			forbidden.emplace(hx+i, hy+j);
		}
	}
	dp[0][0] = 1LL;
	for (ll i = 1LL; i <= n; i++){
		dp[0][i] = !forbidden.count({0LL, i}) && dp[0][i-1];
		dp[i][0] = !forbidden.count({i, 0LL}) && dp[i-1][0];
	}
	for (ll i = 1LL; i <= n; i++){
		for (ll j = 1; j <= m; j++){
			if (forbidden.count({i, j})) dp[i][j] = 0LL;
			else dp[i][j] = dp[i-1][j] + dp[i][j-1];
		}
	}
	printf("%lld", dp[n][m]);
	return 0;
}
2024/5/30 20:47
加载中...