UVA 11624 Fire!(图论BFS)
题意:问你Joe需要最少多长时间能走出一个大火蔓延到网格迷宫。迷宫中存在火源和障碍格。
分析:
朴素的做法是用BFS来模拟Joe的走法,然后看他下一步走的格子是否没有火。(判断该格子在当前时刻有没有火,只需要看看与该格子同行或同列的最近火源是哪个,然后算出起火时间即可。这样算可能会超时)
现在由于火源也是和Joe同样的朝4个方向走的,我们把火源也看成是人,看下是否有一个空闲的边界点是Joe比火源先到达的。
可以证明:Joe和火源同时到达某个点,那么他们肯定会一直同时到达由该点延伸的后续的所有点。
代码中用vis[i][j][0]和d[i][j][0]表示当前格子是否已经被Joe走过且Joe走到(i,j)格子的最短时间是多少.
用vis[i][j][1]和d[i][j][1]表示当前格子是否已经被火源走过,且火源走到(i,j)格子的最短时间是多少.
最后再在所有的边界中找出所有Joe可以到达的空闲格且Joe到达时间比火源到达时间早.输出最小时间即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxr=1000+5;
const int maxc=1000+5;
const int INF=1000000000;
int R,C;
int jr,jc;
struct cell
{
int r,c;
cell(int r,int c):r(r),c(c){}
};
char maze[maxr][maxc];
int vis[maxr][maxc][2], d[maxr][maxc][2];
int dr[]={-1,1,0,0};//对应上下左右
int dc[]={0,0,-1,1};
queue<cell> Q;
void BFS(int kind)
{
while(!Q.empty())
{
cell x= Q.front();Q.pop();
for(int dir=0;dir<4;dir++)
{
int nr=x.r+dr[dir];
int nc=x.c+dc[dir];
if(nr>=0&&nr<R&&nc>=0&&nc<C&&maze[nr][nc]=='.'&&vis[nr][nc][kind]==0)
{
vis[nr][nc][kind]=1;
d[nr][nc][kind]=1+d[x.r][x.c][kind];
Q.push(cell(nr,nc));
}
}
}
}
int ans;
void check(int r,int c)
{
if(vis[r][c][0]==1)
{
if(vis[r][c][1]==0 || (d[r][c][0]<d[r][c][1]) )
ans=min(ans,d[r][c][0]+1);//走到边界还不算出了迷宫,必须走出迷宫才算
}
}
int main()
{
int T;
scanf("%d%*c",&T);
while(T--)
{
vector<cell> Fire;//初始化火源
scanf("%d%d%*c",&R,&C);
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
maze[i][j]=getchar();
if(maze[i][j]=='J')
{
maze[i][j]='.';
jr=i;jc=j;
}
else if(maze[i][j]=='F')
{
Fire.push_back(cell(i,j));
maze[i][j]='.';
}
}
getchar();//读回车符
}
memset(vis,0,sizeof(vis));
d[jr][jc][0]=0;
vis[jr][jc][0]=1;
Q.push(cell(jr,jc));
BFS(0);//Joe走路
for(int i=0;i<Fire.size();i++)
{
d[Fire[i].r][Fire[i].c][1]=0;
vis[Fire[i].r][Fire[i].c][1]=1;
Q.push(Fire[i]);
}
BFS(1);//火源走路
ans=INF;
for(int i=0;i<R;i++){check(i,C-1); check(i,0);}
for(int i=0;i<C;i++){check(0,i); check(R-1,i);}
if(ans==INF) printf("IMPOSSIBLE\n");
else printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
2. 从侧边栏的类别目录找到「图论 BFS」 3. 按照「推荐指数」从大到小进行刷题,「推荐指数」相同,则按照「难度」从易到 4. 拿到题号之后,回到本合集进行
图论DFS,BFS,shortestPath,topoSort,keyPath
讲解了BFS。 这个视频的联系地址可以在这里查看:https://www.acwing.com/problem/search/1/?csrfmiddlewaretoken=TovleMBNSFUoIg1I0cdL4vIKiggOzDXxQl9ELwj0iVTiZ6OyRwzVOnbYGlHNBPU5&search_content=BFS
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
有向图强连通分支(bfs邻接阵形式) 有向图强连通分支(dfs邻接阵形式) 有向图最小点基(邻接阵形式) 图论_匹配\ 二分图最大匹配(hungary邻接表形式) 二分图最大匹配(hungary邻接阵形式) 二分图最大匹配(hungary...
bfsk在高斯信道和锐利多径衰落信道中传输的性能比较,使用simulink!!!!!!!!!
动态内存+BFS #include #include #include #include using namespace std; void BFS(list<int> *the_a,int the_N,int the_S,int *the_b){ int *m=new int[the_N]; for(int k1=0;k1;k1++) m[k1]=0; m[the_S-1]=1; ...
降群法解魔方 哈哈师大 使用双向BFS搜素
simulink BFSK仿真
详细地介绍BFS的思路模式以及用几个案例教授怎么运用BFS去解题。
山东大学2018算法导论图论考试复习总结,只考图论部分所以只有图论部分的总结。 本人于考试周吐血总结,包含的内容如下。 算法导论-图论 复习 优质的复习资料 1 基本的图算法 1.1 图的表示 1.2 BFS:广度优先搜索 ...
现有的分布式文件系统(如HDFS等)无法满足低延迟、高可用、跨地域扩展等方面的需求,所以我们从百度搜索的业务特点出发,开发了自己的分布式文件系统BFS。 设计目标 高可靠、高可用通过将数据副本进行多机房、多...
这是山东大学可视化课程项目,用js实现的BFS和DFS,详细的展示了BFS和DFS的运行过程,网页可交互。
bfsk系统仿真 bfsk系统仿真 bfsk系统仿真
code for bfs algorithm
压缩文件里的“bfs-node.h”是头文件,需要在Visual Studio中附加在头文件。这里采取了有向图的邻接链表表现形式,起作用的bfs函数的代码格式参考了《算法导论》这本书上的伪代码。
DFS和BFS算法的实现,使用C++语言,适合数据结构初学者学习。
C#,图论与图算法,有向图(Direct Graph)广度优先遍历(BFS,Breadth First Search)算法与源程序 图的广度优先遍历(或搜索)类似于树的广度优先遍历(参见本文的方法2)。这里唯一需要注意的是,与树不同,图...
C++ BFS迷宫.cpp
BFS广度优先搜索算法视频演示。宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索...