AOJ 579.期末考试之传纸条

148

题目


Time Limit: 1000 ms
Case Time Limit: 1000 ms 
Memory Limit: 32 MB  
Total Submission: 12  
Submission Accepted: 8  

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


题解



BFS寻路

注意各种边界条件

代码



/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
using namespace std;
 
const int maxn = 105;
 
char map[maxn][maxn];
const int delta[] = {0,0,1,-1};
 
bool Do() {
    int n,m;
    int x1,y1,x2,y2;
    if(scanf("%d%d",&n,&m) == EOF)
        return false;
 
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++)
            map[i][j] = '.';
 
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++) {
            char temp;
            scanf("\n%c\n",&temp);
            if(temp == 'A') {
                x1 = i;
                y1 = j;
            }
            if(temp == 'B') {
                x2 = i;
                y2 = j;
            }
            if(temp == 'T') {
                temp = '#';
                for(int k = 0;k < 4;k++) {
                    int xx = i + delta[k];
                    int yy = j + delta[3 - k];
                    if(xx >= 0 && xx < n && yy >=0 && yy < m)
                        map[xx][yy] = '#';
                }
                for(int k = 2;k < 4;k++) {
                    for(int l = 2;l < 4;l++) {
                        int xx = i + delta[k];
                        int yy = j + delta[l];
                        if(xx >= 0 && xx < n && yy >= 0 && yy < m)
                            map[xx][yy] = '#';
                    }
                }
            }
            if(temp == '#')
                map[i][j] = '#';
        }
    /*
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++)
            printf("%c",map[i][j]);
        printf("\n");
    }
    */
 
    queue <pair<int,int> > Q;
    int len[maxn][maxn] = {0};
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++)
            len[i][j] = -1;
    len[x1][y1] = 0;
    Q.push(pair<int,int>(x1,y1));
    while(!Q.empty()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        if(x == x2 && y == y2)
            break;
        for(int i = 0;i < 4;i++) {
            int xx = x + delta[i];
            int yy = y + delta[3 - i];
            if(xx >= 0 && xx < n && yy>=0 && yy < m && map[xx][yy]=='.' && len[xx][yy] == -1) {
                len[xx][yy] = len[x][y] + 1;
                Q.push(pair<int,int>(xx,yy));
            }
        }
    }
    printf("%d\n",len[x2][y2]);
 
    return true;
}
 
int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论