30分求助,这个记忆化搜索是思路错了还是代码错了?
查看原帖
30分求助,这个记忆化搜索是思路错了还是代码错了?
389844
XjascodoixjqoinOI楼主2021/1/25 13:42
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10;

int n, m, sx, sy, ex, ey, T;
int f[N][N];
int g[N][N];
bool st[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if (v != -1) return v;
    v = 0;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a > 0 && a <= n && b > 0 && b <= m && !g[a][b] && !st[a][b])
        {
            st[a][b] = true;
            v += dp(a, b);
            st[a][b] = false;
        }
    }
    return v;
}

int main()
{
    cin >> n >> m >> T;
    cin >> sx >> sy >> ex >>ey;
    for (int i = 0; i < T; i ++ )
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = 1;
    }
    memset(f, -1, sizeof f);
    f[sx][sy] = 1;
    cout << dp(ex, ey) << endl;
    return 0;
}
2021/1/25 13:42
加载中...