动态规划求助,第三第四WA
查看原帖
动态规划求助,第三第四WA
975789
Crescentrosesama楼主2023/5/4 19:30
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
//dp[x][y]=dp[x-1][y]+dp[x][y-1];
bool Chess[30][30]={false};
long long m, n, a, b;
long long cnt = 0;
long long  dp[30][30] = { 0 };
long long  Solve(int x, int y)
{
	if (dp[x][y] == 0)
	{
		if (Chess[x-1][y])dp[x][y] += Solve(x-1, y);
		if (Chess[x][y-1])dp[x][y] += Solve(x, y-1);
	}
	return dp[x][y];
}
void Dfs(int x, int y)
{
	if (x > m || y > n || x == m && y == n)
	{
		if (x == m && y == n)cnt++;
		return;
	}
	if (Chess[x + 1][y])
		Dfs(x + 1, y);
	if (Chess[x][y + 1])
		Dfs(x, y + 1);
}//刚开始写的深搜,两个TLE
int main()
{
	cin >> m >> n >> a >> b;
	for (int i = 0; i <= m; i++)
		for (int j = 0; j <= n; j++)
			Chess[i][j] = true;
	Chess[a][b] = false;
	Chess[a - 2][b - 1] = Chess[a - 1][b - 2] = Chess[a + 1][b - 2] = Chess[a + 2][b - 1] = Chess[a + 2][b + 1] = Chess[a + 1][b + 2] = Chess[a - 1][b + 2] = Chess[a - 2][b + 1] = false;//马位置标记
	for (int i = 0; i <= m; i++)
		dp[i][0] = 1;
	for (int i = 0; i <= n; i++)
		dp[0][i] = 1;//dp数组初值初始化
	cout << Solve(m,n);
	return 0;
}
2023/5/4 19:30
加载中...