NOI 题库 7218

7218 献给阿尔吉侬的花束

描述

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

输入

第一行是一个正整数T（1 <= T <= 10），表示一共有T组数据。
每一组数据的第一行包含了两个用空格分开的正整数R和C（2 <= R, C <= 200），表示地图是一个R×C的矩阵。
接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。

输出

对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。

样例输入

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

样例输出

5
1
oop!

 1 #include "bits/stdc++.h"
 2 
 3 using namespace std ;
 4 const int maxN = 1e5 + 1e3 ;
 5 const int INF = 2147483647 ; 
 6 
 7 int start_x , start_y , des_x , des_y ;
 8 const int dx [ ] = { 1 , 0 , -1 , 0 } ;
 9 const int dy [ ] = { 0 , 1 , 0 , -1 } ;
10 
11 char mp[ 550 ][ 550 ] ;
12 int pos_x[ maxN ] , pos_y [ maxN ] ,step[ maxN ] ;
13 void Scan ( const int n , const int m ) {
14         getchar ( ) ;
15         for ( int i=1 ; i<=n ; ++i ) {
16                 for ( int j=1 ; j<=m ; ++j ) {
17                         mp[ i ][ j ] = getchar ( ) ;
18                         if ( mp [ i ][ j ] == 'S' ) {
19                                 start_x = i ; 
20                                 start_y = j ;
21                         }
22                         if( mp[ i ][ j ] == 'E' ) {
23                                 des_x = i ;
24                                 des_y = j ; 
25                                 mp[ i ][ j ] = '.' ;
26                         } 
27                 }
28                 getchar ( ) ;
29         }
30 }
31 
32 void BFS ( const int n , const int m ) {
33         int Head = 0 , Tail = 1 ; 
34         bool Get_Target = false ;
35         pos_x[ Tail ] = start_x ;
36         pos_y[ Tail ] = start_y ;
37         step[ Tail ] = 0 ;
38         mp[ start_x ][ start_y ] = '#' ;
39         while ( Head < Tail ) {
40                 ++ Head ;
41                 for ( int i=0 ; i<4 ; ++i ) {
42                         int xx = pos_x[ Head ] + dx[ i ] ;
43                         int yy = pos_y[ Head ] + dy[ i ] ;
44                         if ( xx > 0 && xx <= n && yy >= 0 && yy <= m && ( mp[ xx ][ yy ] == '.' || mp[ xx ][ yy ] == '*' ) ) {
45                                  step[ ++ Tail ] = step[ Head ] + 1 ;
46                                  mp[ xx ][ yy ] = '#' ;
47                                  pos_x [ Tail ] = xx ;
48                                  pos_y [ Tail ] = yy ; 
49                                  if ( xx == des_x && yy == des_y ) {
50                                          Get_Target = true ;
51                                          printf ( "%d
" , step[ Tail ] ) ;
52                                  }
53                         } 
54                 }
55         }
56         if ( !Get_Target ) { printf ( "oop!
" ) ; }
57 }
58 
59 int main ( ) {
60         int N , M , T ;
61         scanf ( "%d" , &T ) ;
62         while (  T-- ) {
63                 scanf ( "%d%d" , &N , &M ) ; 
64                 Scan ( N , M ) ;
65                 BFS ( N , M );
66         }
67 }

View Code

2016-10-19 13:14:49

(完)