信息学奥赛一本通（1256：献给阿尔吉侬的花束）

1256：献给阿尔吉侬的花束

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 7427     通过数: 3067

【题目描述】

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

迷宫用一个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!

【分析】

        典型的迷宫问题，可以用bfs求解，四个方向延伸。

【参考代码】

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
 
using namespace std;

const int N=210;

struct point
{
    int x;       // 坐标
    int y;
    int step;    // 步数
};

int m,n;               //地图尺寸
char a[N][N];          //地图
int vis[N][N];         //访问数组
int dx[4]={0,1,0,-1};  //方向数组，右，下，左，上 
int dy[4]={1,0,-1,0};

int startx,starty;     //起始点坐标
int p,q;               //终点坐标
int flag;
 
void bfs()
{
	queue <point> r;   // 申请队列 
    point s;           // 初始化队列
    s.x=startx;
    s.y=starty;
    s.step=0;
    
    r.push(s);         // 起点入队
    vis[startx][starty]=1;
     
    while(!r.empty())      // 判断队列是否为空 
    {
        point t,tmp;
        t=r.front();
                 
        if(t.x==p && t.y==q)   // 判断是否是终点 
        {
        	flag=true;
            cout << t.step << endl;
            return;
        }
        for(int k=0;k<4;k++)  // 四个方向 
        {
            tmp.x=t.x+dx[k];
            tmp.y=t.y+dy[k];
             
            if(tmp.x>=1 && tmp.x<=m && tmp.y>=1 && tmp.y<=n && a[tmp.x][tmp.y]=='.' && vis[tmp.x][tmp.y]==0)  // 判断能不能走 
            {
                //入队处理
                tmp.step=t.step+1;
                r.push(tmp);           //入队 
                vis[tmp.x][tmp.y]=1;   //标记 
            }
        }
        r.pop();  //拓展完了，需要将队首元素出队
    }
}
int main()
{
    int i,j,t;
 	scanf("%d",&t);
 	while(t--)
 	{
 		memset(vis,0,sizeof(vis));
 		flag=0;
 		cin >> m >> n;
    	for(i=1;i<=m;i++)
    	{
        	for(j=1;j<=n;j++)
        	{
            	cin >> a[i][j];     // '.'表示空地，'#'表示障碍物
            	if(a[i][j]=='S')
            	{
                	startx=i;
                	starty=j;
                	a[i][j]='.';
            	}
            	if(a[i][j]=='E')
            	{
                	p=i;
                	q=j;
                	a[i][j]='.';
            	}
        	}
    	}
    	vis[startx][starty]=1;
    	bfs();
    	if(!flag)
    		cout << "oop!" << endl;
    }
    return 0;
}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1256