1543: 爆炸
时间限制: 1 Sec 内存限制: 64 MB提交: 41 解决: 6
[提交][状态][讨论版]
题目描述
给你一个n行m列的点阵，“#”代表墙，“．”代表空地，“B”代表出发点，“E”代表出口，你从出发点开始，每一步可以走到上、下、左、右四个方向的
相邻空地，问你至少要走多少秒才能走到出口？你的步伐很一致，走一步耗时1秒。这个问题太简单了，加点难度：你身上带有k个炸弹，一个炸弹可以把一堵墙炸
为空地，但墙要2秒后才能变为空地。也就是说，假如现在是时刻t，你在某格子放了一个炸弹，那么该格子在时刻t+l变成空地，你最早在时刻t+2才能进入
该格子。注意：你每次只能把炸弹放在你所在的当前位置的相邻的四个格子，一个炸弹只能炸一堵墙。
有了k个炸弹，你从出发点到终点最少要耗时几秒？如果无法到达，输出-1。
输入
第1行：三个整数n，m'k，l≤n，m≤50,0≤k≤100。接下来是n行m列的点阵，“#”，代表墙，“.”代表空地，“B”代表出发点，“E”代表出口。
输出
一个整数，有了k个炸弹，你从出发点到终点最少要耗时几秒？如果无法到达，输出一1。
样例输入
6 7 1
.....B.
.#####.
.#...#.
.#E#.#.
.###.#.
.......
样例输出
8
提示
第1秒：向左走，到达点(1，5)；
第2秒：在点(2，5)处放一个炸弹；
第3秒：点(2，5)的墙变成空地；
第4秒：向下走，进入点(2，5)；
第5秒：向下走，进入点(3，5)；
第6秒：向左走，进入点(3，4)；
第7秒：向左走，进入点(3，3)；
第8秒：向下走，到达终点(4，3)。
到达任何地方。前者是到的时间短，炸弹数少，后者是到的时间虽然长，但炸弹数多，这两种情况都要讨论；（mxzf0213）
这题看的迷迷糊糊的，之前刷的都是没有拐弯的，直接就可以用bfsac的，这几天做的都是加强版吧，以后远离水题。加油！！！
#include <cstring> #include <vector> #include <cstdio> #include <algorithm> #include <queue> #define fi first #define se second #define pi pair<int,int> #define md make_pair #define ha pair<int,pair<int,pi> > using namespace std; const int inf=0x3f3f3f3f; int n,m,k,ans,vis[55][55],poe[55][55]; char a[55][55]; int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; struct node { int x,y,now,vis; node(int a,int b,int c,int d){ x=a,y=b,now=c,vis=d; } bool operator < (const node &p)const{ return vis>p.vis; } }; void bfs(int f,int g){ node init(f,g,k,1); priority_queue<node> p; p.push(init); vis[f][g]=1;poe[f][g]=k; while(!p.empty()){ node q = p.top();p.pop(); int x=q.x,y=q.y; for(int i=0;i<4;i++){ int l=x+dx[i],r=y+dy[i]; if(l>=0&&l<n&&r>=0&&r<m){ if(a[l][r]=='#'&&q.now&&(!vis[l][r]||vis[l][r]>vis[x][y]+3||poe[l][r]<poe[x][y]-1)){ node u(l,r,q.now-1,q.vis+3); poe[l][r]=q.now-1; vis[l][r]=vis[x][y]+3; p.push(u); } if(a[l][r]=='.'&&(!vis[l][r]||vis[l][r]>vis[x][y]+1||poe[l][r]<poe[x][y])){ node u(l,r,q.now,q.vis+1); poe[l][r]=q.now; vis[l][r]=vis[x][y]+1; p.push(u); } if(a[l][r]=='E') ans=min(ans,q.vis); } } } } int main(){ //freopen("data.in","r",stdin); scanf("%d%d%d",&n,&m,&k); ans=inf; for(int i=0;i<n;i++){ scanf("%s",a[i]); } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='B'){ bfs(i,j);break; } } } if(ans==inf)printf("-1 "); else printf("%d ",ans); }