【BFS】【AOJ-579】期末考试之考试传纸条

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 Output

8
-1

思路：

广度优先搜索把T的八个方向的位置全部换成# 如果替换后不存在AB后肯定-1 否则就BFS 这里要注意判断八个方向中有没有T 否则会把T给覆盖掉造成错误（卡在这地方卡半天...一直WA）

参考代码：

#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
"); 
            continue; 
        } 
        k=bfs(a,b); 
        if(k) 
            printf("%d
",k); 
        else
            printf("-1
"); 
    } 
    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; 
}