原题链接:https://www.luogu.com.cn/problem/P2895
题意解读:所谓安全格子,就是在所有流星坠落之后,没有被烧焦的格子,要计算从起点到这些格子任一一个的最短路径,BFS可以解决。
解题思路:
1、读取数据,先把所有流星坠落点以及周围被烧焦的格子进行标记,得到安全格子
2、从起点开始BFS,每走一步之前,要把该时刻被烧焦的格子进行标记,只能向上、下、左、右移动到没有被烧焦的格子中,且不能越界
3、遍历到任一安全格子,输出步数
注意:
测试点14有一个坑,就是人是可以走到坐标>300的格子的,流星能烧焦的格子坐标最多到301,所以如果人走到坐标302的格子,就能到安全格子。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int M = 50005, N = 305;
struct pos
{
int x, y;
};
bool unsafe[N][N]; //unsafe[i][j]==true表示被烧焦的格子,unsafe[i][j]==false表示安全格子
map<int, vector<pos>> stars; //保存所有时刻出现的流星
bool flag[N][N]; //标记是否烧焦、以及是否走过
int depth[N][N]; //depth[i][j]表示从起点到(i,j)的步数
queue<pos> q;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int m, x, y, t;
void bfs()
{
q.push({0, 0});
flag[0][0] = true;
while(q.size())
{
pos p = q.front(); q.pop();
//如果是安全格子,输出结果
if(!unsafe[p.x][p.y])
{
cout << depth[p.x][p.y];
return;
}
//下一个时刻哪些流星会落地,标记烧焦的格子
vector<pos> s = stars[depth[p.x][p.y] + 1];
for(auto a : s)
{
flag[a.x][a.y] = true;
for(int i = 0; i < 4; i++)
{
int nx = a.x + dx[i], ny = a.y + dy[i];
if(nx >= 0 && nx <= 300 && ny >= 0 && ny <= 300) flag[nx][ny] = true;
}
}
//遍历四个方向
for(int i = 0; i < 4; i++)
{
int nx = p.x + dx[i], ny = p.y + dy[i];
if(!flag[nx][ny] && nx >= 0 && nx <= 302 && ny >= 0 && ny <= 302) //注意人是可以走到300以外的格子的,流星能烧焦的格子最多是301
{
depth[nx][ny] = depth[p.x][p.y] + 1;
flag[nx][ny] = true;
q.push({nx, ny});
}
}
}
cout << -1;
}
int main()
{
cin >> m;
while(m--)
{
cin >> x >> y >> t;
//标记被烧焦格子
unsafe[x][y] = true;
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && nx <= 300 && ny >= 0 && ny <= 300) unsafe[nx][ny] = true;
}
//保存流星
stars[t].push_back({x, y});
}
bfs();
return 0;
}
标签:nx,&&,格子,int,洛谷题,unsafe,Shower,烧焦,Meteor From: https://www.cnblogs.com/jcwy/p/18054319