冰封侠 @ 2022-08-23 19:46:32
我感觉思路是没问题的,但不知道代码哪里错了,求大佬帮忙。代码如下:
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define maxn 310
using namespace std;
int wx[5] = {0, 0, 1, -1}, wy[5] = {-1, 1, 0, 0};
int mapp[maxn][maxn], star[maxn][maxn], vis[maxn][maxn];
int m, ans = 1000000;
struct poi
{
int x, y, t;
};
queue<poi> q;
void time(int sx, int sy, int st)
{
star[sx][sy] = min(star[sx][sy], st);
}
int main()
{
memset(star, 0x7f, sizeof(star));
memset(mapp, -1, sizeof(mapp));
scanf("%d", &m);
for(int i = 1; i <= m; i++)
{
int sx, sy, st;
scanf("%d%d%d", &sx, &sy, &st);
time(sx, sy, st);
for (int j = 0; j < 4; j++)
time(sx + wx[i], sy + wy[i], st);
}
q.push((poi){0, 0, 0});
mapp[0][0] = 0;
vis[0][0] = 1;
while(!q.empty())
{
poi cnt = q.front();
q.pop();
int cntx = cnt.x, cnty = cnt.y, cntt = cnt.t;
for (int i = 0; i < 4; i++)
{
int xx = cntx + wx[i], yy = cnty + wy[i];
if (xx >= 0 && yy >= 0 && vis[xx][yy] == 0 && cntt + 1 < star[xx][yy])
{
vis[xx][yy] = 1;
mapp[xx][yy] = cntt + 1;
q.push((poi){xx, yy, cntt + 1});
}
}
}
for (int i = 0; i < 305; i++)
for (int j = 0; j < 305; j++)
if (star[i][j] > 10000 && mapp[i][j] != -1)
ans = min(ans, mapp[i][j]);
if (ans > 10000) printf("-1");
else printf("%d", ans);
return 0;
}