常规思路只A一个,好奇怪
查看原帖
常规思路只A一个,好奇怪
272780
Scuzs楼主2021/3/30 15:30
#include<iostream>
using namespace std;

const int maxn = 30;
unsigned long long dp[maxn][maxn];
int hx, hy, desx, desy;
int main() {
	cin >> desx >> desy >> hx >> hy;
	for (int i = 0; i <= desx; i++) {
		dp[0][i] = 1;
	}
	for (int i = 0; i <= desy; i++) {
		dp[i][0] = 1;
	}
	dp[hx][hy] = -1;
if(hx+1<=desx&&hy+2<=desy) dp[hx + 1][hy + 2] = -1;
if(hx+1<=desx&&hy-2>=0)	dp[hx + 1][hy - 2] = -1;
if(hx-1>=0&&hy+2<=desy)	dp[hx - 1][hy + 2] = -1;
if(hx-1>=0&&hy-2>=0)	dp[hx - 1][hy - 2] = -1;
if(hx+2<=desx&&hy-1>=0)	dp[hx + 2][hy - 1] = -1;
if(hx+2<=desx&&hy+1<=desy)	dp[hx + 2][hy + 1] = -1;
if(hx-2>=0&&hy+1<=desy)	dp[hx - 2][hy + 1] = -1;
if(hx-2>=0&&hy-1>=0)	dp[hx - 2][hy - 1] = -1;

	for (int i = 1; i <= desx; i++) {
		for (int j = 1; j <= desy; j++) {
			int ex=0;
			if (dp[i][j] == -1) continue;
			else {
				if (dp[i - 1][j] == -1) ex++;
				if (dp[i][j - 1] == -1) ex++;
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1]+ex;
			}
		}
	}
	cout << dp[desx][desy];
	return 0;
}

只A了一个,是哪里出错了哇。思路就是用-1标记马和马拦路的点,用方程dp[i][j]=dp[i-1][j]+dp[i][j-1]填表,因为实际上拦路的点dp[p][q]=0,所以用ex修复一下。

2021/3/30 15:30
加载中...