专栏文章

P1002 [NOIP 2002 普及组] 过河卒 题解

P1002题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioh8r1e
此快照首次捕获于
2025/12/02 19:10
3 个月前
此快照最后确认于
2025/12/02 19:10
3 个月前
查看原文

题意描述

棋盘上 AA 点有一个过河卒,需要走到目标 BB 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
说人话就是:卒在不经过马的控制点的情况下,一共有几种到达 BB 点的方法?

我会搜索!

CPP
#include <bits/stdc++.h>
#define AKIOI ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define AKNOI return 0
#define int long long
#define endl "\n"
using namespace std;
const int N = 2e3 + 100;
const int TMP = 20;
int a[N + TMP][N + TMP], g[N + TMP][N + TMP], ans = 0;
int n, m;
void dfs(int x, int y) {
	if(x > n) return ;
	if(y > m) return ;
	if(x == n && y == m) {
		ans++;
		return;
	}
	if(g[x + TMP][y + TMP] == 0) {
		g[x + TMP][y + TMP] = 1;
		dfs(x + 1, y);
		dfs(x, y + 1);
		g[x + TMP][y + TMP] = 0;
	}
	return ;
}
void book(int x, int y) {
	g[x - 1 + TMP][y - 2 + TMP] = 1; //加一个向右偏移量,防止越界
	g[x - 2 + TMP][y - 1 + TMP] = 1;
	g[x - 2 + TMP][y + 1 + TMP] = 1;
	g[x - 1 + TMP][y + 2 + TMP] = 1;
	g[x + 1 + TMP][y - 2 + TMP] = 1;
	g[x + 2 + TMP][y - 1 + TMP] = 1;
	g[x + 1 + TMP][y + 2 + TMP] = 1;
	g[x + 2 + TMP][y + 1 + TMP] = 1;
	g[x + TMP][y + TMP] = 1;
}
signed main() {
	AKIOI;
	int x, y;
	cin >> n >> m >> x >> y;
	book(x, y);
	dfs(0, 0);
	cout << ans;
	AKNOI;
}
60pts.

我会记搜!

评论

0 条评论,欢迎与作者交流。

正在加载评论...