期末考试之考试传纸条

Description

平时不努力，考试得着急呐。传说中的BT监考老师竟然搬来了信号屏蔽工具，手机不管用啦有木有。不过这难不到大家，cxlove见证了同学们使用传统的作弊方式----传纸条，纸条得从A同学传到B同学处，在一个N*M的教室里，零散着坐着一些同学，监考老师游荡在教室某些位置，能否成功将纸条传到B同学处，且不被老师发现。每一次传纸条不能斜传，只能传给前后左右四个同学，监考老师的监视范围为相邻的八个位置，当纸条传到老师监视范围内就会被逮住了，纸条传到空位置处时传送失败。帮cxlove计算下最少需要多少时间才能完成传纸条。

Input

多组测试数据第一行两个整数，N,M(1<=N,M<=100)，分别表示教室有N*M个位置接下来N行，每行M个字符，表示教室的情况'A'表示纸条的初始位置，'B'表示纸条的目标位置，'.'表示一般同学的位置，'#'表示当前位置没有人坐，'T'表示监考老师。（可能有多个监考老师）

Output

输出仅一个整数，表示需要的最少时间传到B同学处如果不能传达，输出-1

Sample Input

5 5

A.T..

.#..#

.....

####.

....B

1 5

A.T.B

Sample OutputOriginal Transformed

-1

代码如下：

#include "stdafx.h"
#include <stdio.h>
#include <string>
#include <stdlib.h>

int n,m;
char map[105][105];
int ans[105][105];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
typedef struct
{
int x;
int y;
}node;

// 宽度优先遍历
int bfs(node s, node e)
{
node que[10005];
node tt;
int head=0, tail=1, i;
// 把A点的位置赋值给que[0]
que[0]=s;
ans[s.x][s.y]=0;
map[s.x][s.y]='#';
while(head<tail)
{
s=que[head++];
for(i=0; i<4; i++)
{
tt.x=s.x+dir[i][0];
tt.y=s.y+dir[i][1];
if(tt.x>=0&&tt.x<n&&tt.y>=0&&tt.y<m&&map[tt.x][tt.y]!='#')
{
ans[tt.x][tt.y]=ans[s.x][s.y]+1;
if(tt.x==e.x&&tt.y==e.y)
return ans[e.x][e.y];
map[tt.x][tt.y]='#';
que[tail++]=tt;
}
}
}
return 0;
}


int _tmain(int argc, _TCHAR* argv[])
{
// 位置坐标；
int i,j;
// 输入的每个位置的值，学生、老师、还是空位置。
char ch;
// 保存到的是A和B的坐标；
node s,e;
int k1,k2;
int ans;
// 输入座位的行列数；
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(map,0,sizeof(map));
for(i=0; i<n; i++)
{
getchar();
for(j=0; j<m; j++)
{
scanf("%c",&ch);
// 如果输入为A，保留A的坐标
if(ch=='A')
{
s.x=i;
s.y=j;
}
else if(ch=='B')
{
e.x=i;
e.y=j;
}
else if(ch=='T') //监考老师以全都是不可达的
{
for(k1=i-1; k1<=i+1; k1++)
for(k2=j-1; k2<=j+1; k2++)
if(k1>=0&&k1<n&&k2>=0&&k2<m)
map[k1][k2]='#';
}
if(map[i][j]!='#')
map[i][j]=ch;
}
}
if(map[s.x][s.y]=='#'||map[e.x][e.y]=='#')  
        {  
            printf("-1\n");  
            continue;  
        }  
ans = bfs(s,e);
if(ans)
printf("%d\n",ans);
else
printf("-1\n");
}

return 0;
}

秒客网

期末考试之考试传纸条

相关文章