专栏文章
P1002 [NOIP 2002 普及组] 过河卒 题解
P1002题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mioh8r1e
- 此快照首次捕获于
- 2025/12/02 19:10 3 个月前
- 此快照最后确认于
- 2025/12/02 19:10 3 个月前
题意描述
棋盘上 点有一个过河卒,需要走到目标 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
说人话就是:卒在不经过马的控制点的情况下,一共有几种到达 点的方法?
我会搜索!
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;
}
我会记搜!
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...