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

· · 题解

题意描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

说人话就是：卒在不经过马的控制点的情况下，一共有几种到达 B 点的方法?

我会搜索!

#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.

我会记搜！