求助
  • 板块灌水区
  • 楼主封禁用户
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/6/27 18:40
  • 上次更新2023/10/27 22:27:40
查看原帖
求助
595521
封禁用户楼主2022/6/27 18:40

RT

#include <bits/stdc++.h>
using namespace std;

map<pair<int, int>, int> dist;

bool horse(int x, int y, int hx, int hy) {
	if (x == hx - 2 && y == hy - 1) return true;
	if (x == hx - 2 && y == hy + 1) return true;
	if (x == hx - 1 && y == hy - 2) return true;
	if (x == hx - 1 && y == hy + 2) return true;
	if (x == hx + 1 && y == hy - 2) return true;
	if (x == hx + 1 && y == hy + 2) return true;
	if (x == hx + 2 && y == hy - 1) return true;
	if (x == hx + 2 && y == hy + 1) return true;
	if (x == hx && y == hy) return true;
	return false;
}

int solve(int x, int y, int n, int m, int hx, int hy) {
	pair<int, int> pxy = make_pair(x, y);
	if (dist.count(pxy)) return dist[pxy];
	if (x == n && y == m) return 1;
	int ans = 0;
	for (int dx = x; dx <= x + 1; dx++) {
		for (int dy = y; dy <= y + 1; dy++) {
			if (x == dx && y == dy) continue;
			if (0 > dx || dx > n) continue;
			if (0 > dy || dy > m) continue;
			if (horse(dx, dy, hx, hy)) continue;
			ans += solve(dx, dy, n, m, hx, hy);
		}
	}
	return dist[pxy] = ans;
}

int main() {
	int n, m, hx, hy;
	cin >> n >> m >> hx >> hy;
	cout << solve(0, 0, n, m, hx, hy);
	return 0;
}
2022/6/27 18:40
加载中...