社区讨论
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预处理后来不打算用了
明明就是没调出来
88分求条
bfs预处理后来不打算用了
回复
共 2 条回复,欢迎继续交流。
正在加载回复...