Description
平时不努力，考试得着急呐。传说中的BT监考老师竟然搬来了信号屏蔽工具，手机不管用啦有木有。不过这难不到大家，cxlove见证了同学们使用传统的作弊方式----传纸条，纸条得从A同学传到B同学处，在一个N*M的教室里，零散着坐着一些同学，监考老师游荡在教室某些位置，能否成功将纸条传到B同学处，且不被老师发现。每一次传纸条不能斜传，只能传给前后左右四个同学，监考老师的监视范围为相邻的八个位置，当纸条传到老师监视范围内就会被逮住了，纸条传到空位置处时传送失败。
帮cxlove计算下最少需要多少时间才能完成传纸条。
Input
多组测试数据
第一行两个整数，N,M(1<=N,M<=100)，分别表示教室有N*M个位置接下来N行，每行M个字符，表示教室的情况
‘A‘表示纸条的初始位置，‘B‘表示纸条的目标位置，‘.‘表示一般同学的位置，‘#‘表示当前位置没有人坐，‘T‘表示监考老师。（可能有多个监考老师）
第一行两个整数，N,M(1<=N,M<=100)，分别表示教室有N*M个位置接下来N行，每行M个字符，表示教室的情况
‘A‘表示纸条的初始位置，‘B‘表示纸条的目标位置，‘.‘表示一般同学的位置，‘#‘表示当前位置没有人坐，‘T‘表示监考老师。（可能有多个监考老师）
Output
输出仅一个整数，表示需要的最少时间传到B同学处
如果不能传达，输出-1
如果不能传达，输出-1
Sample Input
5 5 A.T.. .#..# ..... ####. ....B 1 5 A.T.B
Sample Output
8 -1思路：
广度优先搜索 把T的八个方向的位置全部换成# 如果替换后不存在AB后 肯定-1
否则就BFS 这里要注意判断八个方向中有没有T 否则会把T给覆盖掉造成错误（卡在这地方卡半天...一直WA）
参考代码：
|
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include <stdio.h> #include <string.h> int
n,m;
typedef
struct
Node
{ int
x;
int
y;
}Node; char
map[111][111];
int
ans[111][111];
int
move[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
int
bfs(Node a,Node b);
int
main()
{ int
k;
Node a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(map,‘#‘,sizeof(map));
memset(ans,0,sizeof(ans));
int
i,j;
for(i=1;i<=n;i++)
scanf("%s",&map[i][1]);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(map[i][j]==‘A‘)
{
a.x=i;
a.y=j;
}
else
if(map[i][j]==‘B‘)
{
b.x=i;
b.y=j;
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(map[i][j]==‘T‘)
{
if(map[i-1][j-1]!=‘T‘)
map[i-1][j-1]=‘#‘;
if(map[i-1][j]!=‘T‘)
map[i-1][j]=‘#‘;
if(map[i-1][j+1]!=‘T‘)
map[i-1][j+1]=‘#‘;
if(map[i][j+1]!=‘T‘)
map[i][j+1]=‘#‘;
if(map[i+1][j+1]!=‘T‘)
map[i+1][j+1]=‘#‘;
if(map[i+1][j]!=‘T‘)
map[i+1][j]=‘#‘;
if(map[i+1][j-1]!=‘T‘)
map[i+1][j-1]=‘#‘;
if(map[i][j-1]!=‘T‘)
map[i][j-1]=‘#‘;
}
}
}
if(map[a.x][a.y]==‘#‘||map[b.x][b.y]==‘#‘)
{
printf("-1\n");
continue;
}
k=bfs(a,b);
if(k)
printf("%d\n",k);
else
printf("-1\n");
}
return
0;
} int
bfs(Node a,Node b)
{ Node queue[100000];
ans[a.x][a.y]=0;
int
i;
int
front=0,rear=1;
queue[front]=a;
map[a.x][a.y]=‘#‘;
while(front<rear)
{
Node newl;
for(i=0;i<4;i++)
{
newl.x=queue[front].x+move[i][0];
newl.y=queue[front].y+move[i][1];
if(newl.x>=1&&newl.x<=n&&newl.y>=1&&newl.y<=m&&map[newl.x][newl.y]!=‘#‘)
{
map[newl.x][newl.y]=‘#‘;
ans[newl.x][newl.y]=ans[queue[front].x][queue[front].y]+1;
queue[rear]=newl;
if(newl.x==b.x&&newl.y==b.y)
return
ans[b.x][b.y];
rear++;
}
}
front++;
}
return
0;
} |