dfs三四测试点过不了,求指教
查看原帖
dfs三四测试点过不了,求指教
1094784
3596006474h楼主2023/11/10 20:06
#include<iostream>
using namespace std;

int m, n, x, y;
int cnt = 0;

//判断卒是不是会被马拦住
bool check(int a, int b, int x, int y) {
    return (a == x && b == y) || (a + 2 == x && b + 1 == y) || (a + 2 == x && b - 1 == y) ||
           (a + 1 == x && b - 2 == y) || (a + 1 == x && b + 2 == y) || (a - 2 == x && b + 1 == y) ||
           (a - 2 == x && b - 1 == y) || (a - 1 == x && b + 2 == y) || (a - 1 == x && b - 2 == y);
}

void dfs(int a, int b) //搜索,
{
    if (a == m && b == n) //抵达终点,搜索结束,方案+1
    {
        cnt++;
        return;
    }

    if (a > m || b > n) //超过了,直接跳出
    {
        return;
    }

    if (check(a, b, x, y)) {
        return;  // 当前位置是马的控制点,不再继续搜索
    }

    dfs(a + 1, b);//往右搜索
    dfs(a, b + 1);//往下搜索
}

int main() {
    cin >> m >> n >> x >> y;
    dfs(0, 0);//从原点开始搜索
    cout << cnt << endl;
    return 0;
}
2023/11/10 20:06
加载中...