only_matthew @ 2021-08-18 11:17:28
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
const int MAXN = 300 + 5, INF = 0x3f3f3f3f;
int time[MAXN][MAXN], d[MAXN][MAXN];
int m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
std::queue<std::pair<int, int> > q;
int main()
{
scanf("%d", &m);
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++)
{
time[i][j] = INF;
d[i][j] = -1;
}
for (int i = 0; i < m; i++)
{
int x, y, t;
scanf("%d %d %d", &x, &y, &t);
time[x][y] = std::min(time[x][y], t);
for (int j = 0; i < 4; j++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && ny >= 0)
{
time[nx][ny] = std::min(time[nx][ny], t);
}
}
}
if (time[0][0] == 0)
{
printf("%d\n", -1);
return 0;
}
q.push(std::make_pair(0, 0));
d[0][0] = 0;
while (q.size())
{
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && ny >= 0 && d[nx][ny] == -1 && d[x][y] + 1 < time[nx][ny])
{
d[nx][ny] = d[x][y] + 1;
if (time[nx][ny] == INF)
{
printf("%d\n", d[nx][ny]);
return 0;
}
q.push(std::make_pair(nx, ny));
}
}
}
printf("%d\n", -1);
return 0;
}
by immix @ 2021-08-18 18:37:34
Line 25~32中
for (int j = 0; i < 4; j++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && ny >= 0)
{
time[nx][ny] =
std::min(time[nx][ny], t);
}
}
for里面i改为j dx和dy里面也改成j
for (int j = 0; j < 4; j++)
{
int nx = x + dx[j], ny = y + dy[j];
if (nx >= 0 && ny >= 0)
{
time[nx][ny] =
std::min(time[nx][ny], t);
}
}
by only_matthew @ 2021-08-19 11:52:17
@linlexiao 非常感谢,我一直找不到原因,原来是粗心,把i,j弄混了