dfs记忆化搜索写法
查看原帖
dfs记忆化搜索写法
972543
wyxc楼主2024/4/5 15:58
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 500;

int ex, ey, m, n;
LL cnt[N][N];
vector<PII> point;

void work(int x, int y)
{
	int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1}, dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};
	point.push_back({x, y});
	for (int i = 0; i < 8; i ++ )
		point.push_back({x + dx[i], y + dy[i]});	
}

bool check(int x, int y)
{
	if (x < 0 || y < 0) return false;
	for (auto item : point)
		if (x == item.first && y == item.second) return false;
	return true;
}

LL dfs(int x, int y)
{
	LL ans = 0;
	if (cnt[x][y] != -1) return cnt[x][y];
	if (check(x - 1, y)) 
		ans += dfs(x - 1, y);
	if (check(x, y - 1)) 
		ans += dfs(x, y - 1);
	return cnt[x][y] = ans;
}

int main()
{
	cin >> ex >> ey >> n >> m;
	work(n, m); // 把所有的拦截点预处理出来
	memset(cnt, -1, sizeof cnt);
	cnt[0][0] = 1;
	cout << dfs(ex, ey) << endl;
	return 0;
}
2024/4/5 15:58
加载中...