社区讨论

88分求条

P1535[USACO08MAR] Cow Travelling S参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhjdggqv
此快照首次捕获于
2025/11/04 00:46
4 个月前
此快照最后确认于
2025/11/04 00:46
4 个月前
查看原帖

88分求条!!

CPP
// #define DEBUG
#ifdef DEBUG
#define LOG(x) std::cout << x;
#else
#define LOG(x)
#endif
#include <bits/stdc++.h>
#define int long long
using namespace std;
/* Const */
struct node
{
    int x, y, step;
};
const int N = 100;

/* Variable */
int n, m, t;
node s;
node d;
int mp[N][N];
int step[N][N]; // for bfs
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int dp[105][105][20];
/* Function */
bool check1(int x, int y)
{
    if (x <= 0 || x > n || y <= 0 || y > m)
        return false;
    if (step[x][y])
        return false;
    if (mp[x][y])
        return false;
    return true;
}
bool check2(int x, int y)
{
    if (x <= 0 || x > n || y <= 0 || y > m)
        return false;
    if (mp[x][y])
        return false;
    return true;
}
// void bfs(int st_x, int st_y)
// {
//     queue<node> q;
//     q.push({st_x, st_y, 0});
//     step[st_x][st_y] = 1; // 起点先打上标记
//     while (q.size())
//     {
//         node z = q.front();
//         q.pop();
//         for (int i = 0; i < 4; i++)
//         {
//             int xx = z.x + dx[i];
//             int yy = z.y + dy[i];
//             if (check1(xx, yy))
//             {
//                 step[xx][yy] = z.step + 1;
//                 q.push({xx, yy, z.step + 1});
//             }
//         }
//     }
//     step[st_x][st_y] = 0; // 恢复起点到起点的步数为0
//     return;
// }
int dfs(int x, int y, int rt)
{
    LOG(1 << endl);
    // if (step[x][y] > rt)
    //     return 0;
    // if (step[x][y] == rt)
    //     return 1;
    if (dp[x][y][rt] != -1)
    {
        LOG(dp[x][y][rt] << endl);
        return dp[x][y][rt];
    }
    if (rt == 0)
    {
        if (x == d.x && y == d.y)
            return dp[x][y][rt] = 1;
        return dp[x][y][rt] = 0;
    }
    int sum = 0;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (check2(xx, yy))
        {
            sum += dfs(xx, yy, rt - 1);
        }
    }
    dp[x][y][rt] = sum;
    return sum;
}
signed main()
{
    //freopen("P1535_4.in", "r", stdin);
    //freopen("my.out", "w", stdout);
    cin >> n >> m >> t;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            mp[i][j] = (c == '*' ? 1 : 0);
        }
    }
    cin >> s.x >> s.y >> d.x >> d.y;
    // bfs(s.x, s.y);
    cout << dfs(s.x, s.y, t);
    // system("pause");
    return 0;
}
谁能告诉我为什么本地第四个点是过的,oj不给过啊:(
88分求条
bfs预处理后来不打算用了
明明就是没调出来

回复

2 条回复,欢迎继续交流。

正在加载回复...