描述 Description
今年秋天，约翰带着奶牛们去玩玉米迷宫。迷宫可分成 NxM 个格子，有些格子种了玉米，种宥玉米的格子无法通行。迷宫的四条边界上都是种了玉米的格子，其屮只有一个格子没种，那就是出口。在这个迷宫里，有一些神奇的传送点 6 每个传送点由一对点组成，一旦走入传送点的某个结点，机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的，如果你定到了另一头，机器也会把你送回来。
奶牛在一个单位的时间内只能向相邻的四个方向移动一格，不过传送机传送是瞬间完成的。
现在 W 西在迷宫里迷路了，她只知道目前的位罝在哪里，请你帮助她用最短的时间走出 迷宫吧。
描述了迷宫第 i 行的信息。其中 “#” 代 表不能通行的玉米地，“.” 代表可以通行的草地，“@” 代表贝西的起始位罝，“=” 代表迷宫出口，大写字母 “A” 到“Z”总是成对出现的，代表一对传送点.
输出格式 OutputFormat
第一行：一个整数，表示贝西走出迷宫的最短时间，保证逃离迷宮的路线一定存在.
样例输入 SampleInput
37 70
######################################################################
#….#TCP#…………………………………………………..#
#….#####…..#……#……………………………………….#
#………….#.#….#.#………………………………………#
#…………..######W#……………………………………….#
#………….#……..#..##############################………….#
#…………#..V….V..#..#……………………….#..#…#…..#
#………….#……..#….#……………………….#..#.#.#….#
#………….#..X##X..#..#……………W……………#..#…#…#
#…………#…N##N…#..#………………………..#………..#
#……..MOO..#..@…..#….#.#.#.#……………….#.#…………#
#…………..########…..#.#.#.##############.#.#..#.#…………#
#………………………#.#.#.#………….#.#.#.#.#…………#
#…….#########………..#.#.#.#……………..#.#.#…………#
#……#………#……….#.#.#.#……………..#.#.#…………#
#..#.#.#G#R#A#S#S#.#.#……#.#.#.#……………..#.#I#…………#
#..###################……#T#C#P#……………..#I#G#…………#
#……………………….#.#.#……………….#.#………….#
#…………………………………………………………..#
#…………………………………………………………..#
#……########……..########…….#………..#………..#……#
#…..#……………#R……A#…….#………#.#………#…….#
#…..#……………#……..#……..#…….#…#…….#……..#
#…..#……………#……..#………#…..#…..#…..#………#
#…..#……………#……..#……….#…#…….#…#……….#
#…..#……………#..M…..#………..#.#………#.#………..#
#……########……..########………….#………..#…………#
#…………………………………………………………..#
#…………………………………………………………..#
#…………………………………………………………..#
####################################################################.#
#…………………………………………………………..#
##.###################################################################
#..#F#ZD#.#Y#.#JL#.#…#QJ#.#.#.#.#EK#….#.L#………….#BQ#……#
#.##Z####.#U#.####.#.#.####.#.#.#.####.#..####………….####.####.#
#….#DE#.###.#UH#…#.#HK#.#.#.#.#F…#……………………#BY#.#
####################################################################=#
样例输出 SampleOutput
232
代码 Code
bfs。遇到传送门的时候修改一下对应的坐标即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
const int dx[5]={0,0,0,1,-1};
const int dy[5]={0,1,-1,0,0};
map < char,pair<int,int> > m1,m2;
char a[305][305],ch;
bool used[305][305];
struct point
{
int x,y,z;
};
deque <point> f;
pair <int,int> endp;
inline void change(int &x,int &y)
{
map < char,pair<int,int> > ::iterator i,j;
if (!m1.count(a[x][y])) return ;
i=m1.find(a[x][y]);
j=m2.find(a[x][y]);
if (i->second==make_pair(x,y))
{
x=j->second.first;
y=j->second.second;
return ;
}
if (j->second==make_pair(x,y))
{
x=i->second.first;
y=i->second.second;
return ;
}
}
inline int bfs()
{
int i,j,t,tx,ty;
while (!f.empty())
{
x=f.front().x;y=f.front().y;z=f.front().z;f.pop_front();
if (endp==make_pair(x,y)) return z;
for (i=1;i<=4;i++)
{
tx=x+dx[i];ty=y+dy[i];
if (a[tx][ty]!='=' && a[tx][ty]!='.' && a[tx][ty]!='#' && a[tx][ty]!='@') change(tx,ty);
if (!used[tx][ty])
{
used[tx][ty]=true;
if (!f.empty() && z+1<f.front().z)
{
f.push_front((point){tx,ty,z+1});
}
else f.push_back((point){tx,ty,z+1});
}
}
}
}
int main()
{
memset(used,false,sizeof(used));
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
for (j=1;j<=m;j++)
{
if (a[i][j]=='@')
{
f.push_back((point){i,j,0});
continue;
}
if (a[i][j]=='=')
{
endp=make_pair(i,j);
continue;
}
if (a[i][j]=='#')
{
used[i][j]=true;
continue;
}
if (a[i][j]!='.')
{
if (m1.count(a[i][j])) m2.insert(make_pair(a[i][j],make_pair(i,j)));
else m1.insert(make_pair(a[i][j],make_pair(i,j)));
}
}
}
printf("%d\n",bfs());
return 0;
}