4AC 1WA 求帮调
查看原帖
4AC 1WA 求帮调
1264654
cleversheep2011楼主2024/8/9 22:33
#include <iostream>
#define ll long long
using namespace std;

ll dfs(ll memory[20][20], int cntrlpnt[9][2], int ax, int ay, int bx, int by)//dfs的函数
{
    if (ax > bx || ay > by)//超出搜索范围那自然就是0
    {
        return 0;
    }
    if (memory[ax][ay] != -1)//如果已经被搜索过值 那么直接返回值(记忆化搜索)
    {
        return memory[ax][ay];
    }
    if (ax == bx && ay == by)//如果找到了 则返回1 代表找到一个结果
    {
        memory[ax][ay] = 1;
        return 1;
    }
    //状态转移方程f(x,y)=f(x+1,y)+f(x,y+1)
    memory[ax][ay] = dfs(memory, cntrlpnt, ax + 1, ay, bx, by) + dfs(memory, cntrlpnt, ax, ay + 1, bx, by);
    return memory[ax][ay];
}

int main()
{
    int bx, by, hx, hy;
    cin >> bx >> by >> hx >> hy;
    int cntrlpnt[9][2] = {{hx, hy}, //马的控制点
                          {hx + 1, hy + 2},
                          {hx + 1, hy - 2},
                          {hx - 1, hy + 2},
                          {hx - 1, hy - 2},
                          {hx + 2, hy + 1},
                          {hx + 2, hy - 1},
                          {hx - 2, hy + 1},
                          {hx - 2, hy - 1}};
    ll memory[20][20]; //记忆化搜索
    for (int i = 0; i < 20; i++) //全部初始化为-1 代表未搜索
    {
        for (int j = 0; j < 20; j++)
        {
            memory[i][j] = -1;
        }
    }
    for (int i = 0; i < 9; i++)//将马的控制点标为0 因为没法走到马的上面
    {
        int x = cntrlpnt[i][0];
        int y = cntrlpnt[i][1];
        if (x >= 0 && x <= 20 && y >= 0 && y <= 20)//检查马的控制点是否有效
        {
            memory[x][y] = 0;
        }
    }
    cout << dfs(memory, cntrlpnt, 0, 0, bx, by) << endl;
    return 0;
}
2024/8/9 22:33
加载中...