2603 逃出城堡
小Biu被困在一个城堡中,城堡可以看成一个大小为n*n的二维平面上的网格图,
每一个格子要么为平地,要么为墙壁,要么为毒区,而且作为毒区的格子,每
一秒会向他周围的上下左右四个格子扩散毒气(毒气不能穿过墙壁)。现在小Biu
身负重任,最开始小Biu在某一个平地上,他每一秒可以向他上下左右四个格子
中的作为平地的格子移动一步,他想知道如果不能穿越墙壁,也不能接触有毒
气的格子(如果毒气和小Biu同时到达某个平地,也算接触),他最少需要多长时间
才能逃出城堡,只要从任何一个边缘走出城堡都算逃出城堡。
如图所示的数据中,只要小Biu先向右移动两步,再向下移动两步,即可逃出城,所以答案为4。
输入
第1行:一个整数n,表示城堡的大小是一个n*n的网格图。(1<=n<=1000) 第2-n+1行:每一行有n个字符,'.'表示平地,'*'表示有毒气的格子,'#'表示墙壁,'S'表示小Biu最开始的 位置。输出
输出一个整数表示答案,如果小Biu不能逃出城堡则输出"IMPOSSIBLE"(不带引号)。输入样例
5 .*... ....# .*..# #S..# .##.# 6 ###### ##S### ...... ..*... ###### ######输出样例
4 IMPOSSIBLE
思路:
暴力一点可以两次bfs,一次毒气走,一次人走。
技巧一点可以一次bfs,人和毒气同时走,但是同一阶段,毒气先走人再走。
bfs注意一下稍加区分即可。
两次bfs代码实现:
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<cstdio>
#include<algorithm>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e5+100;
const int M=2e6+100;
const int mod=1e9+7;
int xx[5]= {0,1,-1,0,0};
int yy[5]= {0,0,0,1,-1};
int dp[1010][1010];
char mp[1010][1010];
struct Node {
int x,y,step;
Node(int a,int b,int c) {
x=a;
y=b;
step=c;
}
Node() { }
};
queue<Node>qc;
int flag[1010][1010];
bool judge(int x,int y,int s) {
if(mp[x][y]=='*'||mp[x][y]=='#'||flag[x][y]||dp[x][y]<=s)return 0;
return 1;
}
int sol(int n,int bx,int by) {
if(mp[bx][by]=='#'||mp[bx][by]=='*')return 0;
while(qc.size())qc.pop();
memset(flag,0,sizeof(flag));
qc.push(Node(bx,by,0));
flag[bx][by]=1;
while(qc.size()) {
Node p=qc.front();
qc.pop();
for(int i=1; i<=4; i++) {
int tmpx=p.x+xx[i];
int tmpy=p.y+yy[i];
int step=p.step+1;
if(tmpx==0||tmpy==0||tmpx==n+1||tmpy==n+1)return step;
if(judge(tmpx,tmpy,step)) {
flag[tmpx][tmpy]=1;
qc.push(Node(tmpx,tmpy,step));
}
}
}
return 0;
}
queue<Node>qc2;
void init(int n) {
while(qc2.size())qc2.pop();
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(mp[i][j]=='*') {
qc2.push(Node(i,j,0));
flag[i][j]=1;
dp[i][j]=0;
}
}
}
while(qc2.size()) {
Node p=qc2.front();
qc2.pop();
for(int i=1; i<=4; i++) {
int tmpx=p.x+xx[i];
int tmpy=p.y+yy[i];
int step=p.step+1;
if(mp[tmpx][tmpy]=='*'||mp[tmpx][tmpy]=='#'||dp[tmpx][tmpy]<=step||flag[tmpx][tmpy]) {
continue;
} else if(!(tmpx>=1&&tmpx<=n&&tmpy>=1&&tmpy<=n))continue;
flag[tmpx][tmpy]=1;
dp[tmpx][tmpy]=min(dp[tmpx][tmpy],step);
qc2.push(Node(tmpx,tmpy,step));
}
}
}
int main() {
#ifdef MYHOME
freopen("input.txt","r",stdin);
#endif
int n,bx,by;
string str;
while(cin>>n) {
memset(dp,INF,sizeof(dp));
memset(flag,0,sizeof(flag));
for(int i=1; i<=n; i++) {
cin>>str;
for(int j=1; j<=n; j++) {
mp[i][j]=str[j-1];
if(str[j-1]=='S') {
bx=i;
by=j;
}
}
}
init(n);
int tmp=sol(n,bx,by);
if(tmp)cout<<tmp<<endl;
else cout<<"IMPOSSIBLE"<<endl;
}
return 0;
}
一次多源点bfs题解:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#define itn int
#define reaD read
#define N 1005
using namespace std;
int n, x, y, ans = 0x3f3f3f3f;
int u[4] = { -1, 0, 1, 0 }, v[4] = { 0, 1, 0, -1 };
struct node {
int x, y, t, opt;
};
bool vis[N][N];
char mp[N][N];
queue<node> q;
inline int read() {
int x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') {
if (c == '-') w = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * w;
}
void bfs() {
while(!q.empty()) {
node tmp = q.front();
q.pop();
int x = tmp.x, y = tmp.y, t = tmp.t;
for(int i = 0; i < 4; i++) {
int tx = x + u[i], ty = y + v[i];
if(tx < 1 || tx > n || ty < 1 || ty > n) {
if(tmp.opt) {
ans = t + 1;
return;
} else continue;
}
if(vis[tx][ty]) continue;
q.push((node) {
tx, ty, t + 1, tmp.opt
});
vis[tx][ty] = 1;
}
}
}
int main() {
n = reaD();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
mp[i][j] = getchar();
if(mp[i][j] == '\n') mp[i][j] = getchar();
if(mp[i][j] == '*') {
vis[i][j] = 1;
q.push((node) {
i, j, 0, 0
});
}
if(mp[i][j] == '#')
vis[i][j] = 1;
if(mp[i][j] == 'S')
x = i, y = j;
}
vis[x][y] = 1;
q.push((node) {
x, y, 0, 1
});
bfs();
if(ans == 0x3f3f3f3f) puts("IMPOSSIBLE");
else printf("%d\n", ans);
return 0;
}
THE END;
今天的文章
逃出城堡攻略_hogwarts story格兰芬多线[通俗易懂]分享到此就结束了,感谢您的阅读。今天的文章
逃出城堡那个游戏叫什么名字?_逃离城堡分享到此就结束了,感谢您的阅读。今天的文章
逃出城堡游戏攻略_逃离遗弃的城堡过关教程分享到此就结束了,感谢您的阅读。今天的文章逃出了城堡_地下城堡2遗弃傀儡怎么选分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/67888.html