bfs hrbust 2188

98 阅读 0 评论 65 点赞

我是靠谱客的博主彩色飞鸟，这篇文章主要介绍bfs hrbust 2188，现在分享给大家，希望可以做个参考。

星际旅行

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 112(44 users)

Total Accepted: 55(41 users)

Rating:

Special Judge: No

Description

小z在星际旅行中，他想从当前起始点到达目的地，他可以上下左右的移动，并且每移动一格需要花费一单位时间，

星际中有许多危险的地方不可以走，还有许多的黑洞，你可以不花费任何时间从一个黑洞瞬间到达其它任何一个黑洞，

请你帮助小z计算从当前起始点到目的地最少需要多少单位时间。

Input

第一行是一个整数T,代表T组测试数据。

对于每组测试数据，首先是两个整数n,m代表星际地图(1<=n<=100, 1<=m<=100)

接下来是一个n*m的地图。

'O' 代表黑洞。

'#' 代表不可以走的地方。

'.' 代表普通的空间。

'S' 代表起始点,有且只有一个。

'E' 代表目的地,有且只有一个。

Output

对于每组测试数据，如果小z可以到达目的地，则输出需要的最少时间，否则输出"impossible"。

Sample Input

3 4

SO..

....

..OE

3 3

#S#

###

E##

Sample Output

impossible

复制代码

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
char map[105][105];
int n,m;
int turn[105][105];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct node{
int x,y,step;
};node u,v;
int judge(int x, int y)
{
if(x>=n||x<0||y>=m||y<0||map[x][y] == '#')
return 0;
return 1;
}
int bfs(int x,int y, int x0,int y0)
{
queue<node>s;
u.x = x;
u.y = y;
u.step = 0;
s.push(u);
while (!s.empty())
{
u = s.front();
s.pop();
if (u.x == x0 && u.y == y0) return u.step;
for (int i = 0; i < 4; i++)
{
v.x = u.x + dx[i];
v.y = u.y + dy[i];
v.step = u.step + 1;
if(judge(v.x,v.y))
{
if(map[v.x][v.y] == 'O')
{
for(int j = 0; j < n;j ++)
for(int k = 0; k < m; k++)
if(map[j][k] == 'O')
{
v.x = j;
v.y = k;
if(judge(v.x,v.y))
s.push(v);
if (u.x == x0 && u.y == y0) return u.step;
}
map[v.x][v.y] = '#';
}
else
{
map[v.x][v.y] = '#';
s.push(v);
}
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(turn,0,sizeof turn);
scanf("%d%d",&n,&m);
for(int i = 0; i < n;i ++)
scanf("%s",map[i]);
int startx,starty;
int endx,endy;
int count = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(map[i][j] == 'S') startx = i,starty = j;
if(map[i][j] == 'E') endx = i, endy = j;
if(map[i][j] == '#') turn[i][j] = 1;
}
}
int ans = bfs(startx,starty,endx,endy);
if(ans == -1)
printf("impossiblen");
else
printf("%dn",ans);
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
char map[105][105];
int n,m;
int turn[105][105];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct node{
int x,y,step;
};node u,v;
int judge(int x, int y)
{
if(x>=n||x<0||y>=m||y<0||map[x][y] == '#')
return 0;
return 1;
}
int bfs(int x,int y, int x0,int y0)
{
queue<node>s;
u.x = x;
u.y = y;
u.step = 0;
s.push(u);
while (!s.empty())
{
u = s.front();
s.pop();
if (u.x == x0 && u.y == y0) return u.step;
for (int i = 0; i < 4; i++)
{
v.x = u.x + dx[i];
v.y = u.y + dy[i];
v.step = u.step + 1;
if(judge(v.x,v.y))
{
if(map[v.x][v.y] == 'O')
{
for(int j = 0; j < n;j ++)
for(int k = 0; k < m; k++)
if(map[j][k] == 'O')
{
v.x = j;
v.y = k;
if(judge(v.x,v.y))
s.push(v);
if (u.x == x0 && u.y == y0) return u.step;
}
map[v.x][v.y] = '#';
}
else
{
map[v.x][v.y] = '#';
s.push(v);
}
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(turn,0,sizeof turn);
scanf("%d%d",&n,&m);
for(int i = 0; i < n;i ++)
scanf("%s",map[i]);
int startx,starty;
int endx,endy;
int count = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(map[i][j] == 'S') startx = i,starty = j;
if(map[i][j] == 'E') endx = i, endy = j;
if(map[i][j] == '#') turn[i][j] = 1;
}
}
int ans = bfs(startx,starty,endx,endy);
if(ans == -1)
printf("impossiblen");
else
printf("%dn",ans);
}
}