USACO 2011 Open Silver 1.Corn Maze

传送门

题目描述:

今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子,有些格子种了玉 米,种有玉米的格子无法通行。迷宫的四条边界上都是种了玉米的格子,其屮只有一个格子 没种,那就是出口。
在这个迷宫里,有一些神奇的传送点。每个传送点由一对点组成,一旦 走入传送点的某个结点,机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的,如果你定到了另一头,机器也会把你送回来。奶牛在一个单位的时间内只能向相邻的四个方向移动一格,不过传送机传送是瞬间完成 的。
现在W西在迷宫里迷路了,她只知道目前的位罝在哪里,请你帮助她用最短的时间走出 迷宫吧。

Sample Input

5 6 
###=## 
#.W.## 
#.#### 
#[email protected]## 
######

Sample Output

3

思路:

存储所有传送门;唯一注意的是当搜索到传送门时,强制传送;
剩下的全是暴力和模板。一道BFS好题QAQ

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int a[500][500];
int zm[30][5];
bool book[500][500];
char s[500];
int n,m;
int l1,l2,r1,r2;
struct your
{
    int x,y,sum;
};
int dx[6]={0,-1,0,0,1};
int dy[6]={0,0,-1,1,0};
void BFS()
{
    queue<your>q;your nmp;
    nmp.x=l1,nmp.y=r1,nmp.sum=0;
    q.push(nmp),book[l1][r1]=1;
    while(q.size())
    {
        nmp=q.front();q.pop();
        for(int i=1;i<=4;i++)
        {
            int dxx=nmp.x+dx[i],dyy=nmp.y+dy[i];
            if(dxx<1||dxx>n||dyy<1||dyy>m)
            	continue;
            if(dxx==l2&&dyy==r2)
            {
                printf("%d",nmp.sum+1);
                return ;
            }
            if(a[dxx][dyy]!=-1&&book[dxx][dyy]==0)
            {
                book[dxx][dyy]=1;
                your temp;
                if(a[dxx][dyy]>0)
                {
                    if(zm[a[dxx][dyy]][1]==dxx&&zm[a[dxx][dyy]][2]==dyy)
                    {
                        temp.x=zm[a[dxx][dyy]][3];
						temp.y=zm[a[dxx][dyy]][4];
						temp.sum=nmp.sum+1;
                    }
                    else 
                    {
	                    temp.x=zm[a[dxx][dyy]][1];
						temp.y=zm[a[dxx][dyy]][2];
						temp.sum=nmp.sum+1;
                    }
                }
                else 
				{
					temp.x=dxx;
					temp.y=dyy;
					temp.sum=nmp.sum+1;
				}
                q.push(temp);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",&s[0]);
        for(int j=0;j<m;j++)
        {
            if(s[j]=='#')a[i][j+1]=-1;
            if(s[j]=='@')l1=i,r1=j+1;
            if(s[j]=='=')l2=i,r2=j+1;
            if(s[j]>='A'&&s[j]<='Z')
            {
                a[i][j+1]=s[j]-'A'+1;
                zm[ s[j]-'A'+1 ][++zm[ s[j]-'A'+1 ][0]]=i;
                zm[ s[j]-'A'+1 ][++zm[ s[j]-'A'+1 ][0]]=j+1;
            }
        }
    }
    BFS();
}

发表评论

邮箱地址不会被公开。 必填项已用*标注