AOJ 579.期末考试之传纸条

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

Original Transformed
5 5
A.T..
.#..#
.....
####.
....B
1 5
A.T.B
Sample Output

Original Transformed
8
-1

BFS寻路

注意各种边界条件

  1 /*
  2 By:OhYee
  3 Github:OhYee
  4 Email:oyohyee@oyohyee.com
  5 */
  6 #include <cstdio>
  7 #include <algorithm>
  8 #include <cstring>
  9 #include <cmath>
 10 #include <string>
 11 #include <iostream>
 12 #include <vector>
 13 #include <list>
 14 #include <queue>
 15 #include <stack>
 16 using namespace std;
 17  
 18 #define REP(n) for(int o=0;o<n;o++)
 19  
 20 const int maxn = 105;
 21  
 22 char map[maxn][maxn];
 23 const int delta[] = {0,0,1,-1};
 24  
 25 bool Do() {
 26     int n,m;
 27     int x1,y1,x2,y2;
 28     if(scanf("%d%d",&n,&m) == EOF)
 29         return false;
 30  
 31     for(int i = 0;i < n;i++)
 32         for(int j = 0;j < m;j++)
 33             map[i][j] = '.';
 34  
 35     for(int i = 0;i < n;i++)
 36         for(int j = 0;j < m;j++) {
 37             char temp;
 38             scanf("
%c
",&temp);
 39             if(temp == 'A') {
 40                 x1 = i;
 41                 y1 = j;
 42             }
 43             if(temp == 'B') {
 44                 x2 = i;
 45                 y2 = j;
 46             }
 47             if(temp == 'T') {
 48                 temp = '#';
 49                 for(int k = 0;k < 4;k++) {
 50                     int xx = i + delta[k];
 51                     int yy = j + delta[3 - k];
 52                     if(xx >= 0 && xx < n && yy >=0 && yy < m)
 53                         map[xx][yy] = '#';
 54                 }
 55                 for(int k = 2;k < 4;k++) {
 56                     for(int l = 2;l < 4;l++) {
 57                         int xx = i + delta[k];
 58                         int yy = j + delta[l];
 59                         if(xx >= 0 && xx < n && yy >= 0 && yy < m)
 60                             map[xx][yy] = '#';
 61                     }
 62                 }
 63             }
 64             if(temp == '#')
 65                 map[i][j] = '#';
 66         }
 67     /*
 68     for(int i = 0;i < n;i++) {
 69         for(int j = 0;j < m;j++)
 70             printf("%c",map[i][j]);
 71         printf("
");
 72     }
 73     */
 74  
 75     queue <pair<int,int> > Q;
 76     int len[maxn][maxn] = {0};
 77     for(int i = 0;i < n;i++)
 78         for(int j = 0;j < m;j++)
 79             len[i][j] = -1;
 80     len[x1][y1] = 0;
 81     Q.push(pair<int,int>(x1,y1));
 82     while(!Q.empty()) {
 83         int x = Q.front().first;
 84         int y = Q.front().second;
 85         Q.pop();
 86         if(x == x2 && y == y2)
 87             break;
 88         for(int i = 0;i < 4;i++) {
 89             int xx = x + delta[i];
 90             int yy = y + delta[3 - i];
 91             if(xx >= 0 && xx < n && yy>=0 && yy < m && map[xx][yy]=='.' && len[xx][yy] == -1) {
 92                 len[xx][yy] = len[x][y] + 1;
 93                 Q.push(pair<int,int>(xx,yy));
 94             }
 95         }
 96     }
 97     printf("%d
",len[x2][y2]);
 98  
 99     return true;
100 }
101  
102 int main() {
103     while(Do());
104     return 0;
105 }