2523: 【普及/提高-】【P1825】Corn Maze S
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
奶牛们去一个 玉米迷宫，。
迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。
如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。
玉米迷宫除了唯一的一个出口都被玉米包围。
迷宫中的每个元素都由以下项目中的一项组成：
-
玉米，
#表示，这些格子是不可以通过的。 -
草地，
.表示，可以简单的通过。 - 传送装置，每一对大写字母 到 表示。
-
出口，
=表示。 -
起点，
@表示
奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 个单位时间。从装置的一个结点到另一个结点不花时间。
输入
第一行：两个用空格隔开的整数 和 。
第 行：第 行描述了迷宫中的第 行的情况（共有个字符，每个字符中间没有空格）。
输出
一个整数，表示起点到出口所需的最短时间。
样例输入 复制
5 6
###=##
#.W.##
#.####
#.@W##
######样例输出 复制
3提示
例如以下矩阵，。
###=##
#.W.##
#.####
#.@W##
###### 唯一的一个装置的结点用大写字母 表示。
最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费 个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了 个单位时间。
#include<bits/stdc++.h>
using namespace std;
struct point {
int x,y,step;
};
struct mark {
int x1,y1,x2,y2;
}ms[100];
int main(){
int n,m,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char maze[305][305],tc;
queue<point> q;
cin>>n>>m;
for (int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
cin>>maze[i][j];
tc=maze[i][j];
if (tc>='A'&&tc<='Z') {
if(ms[tc].x1==0) ms[tc].x1=i,ms[tc].y1=j;
else ms[tc].x2=i,ms[tc].y2=j;
}else if(tc=='@') {
q.push(point{i,j,0});
maze[i][j]='#';
}
}
}
while(!q.empty()) {
point p=q.front();
q.pop();
for(int i=0;i<4;i++) {
int x=p.x+dx[i],y=p.y+dy[i];
tc=maze[x][y];
if(tc=='#'||x<1||y<1||x>n||y>m) continue;
if(tc=='.') {
q.push(point{x,y,p.step+1});
maze[x][y]='#';
continue;
}
if(tc=='=') {
cout<<p.step+1;
return 0;
}
if(ms[tc].x1==x&&ms[tc].y1==y) {
q.push(point{ms[tc].x2,ms[tc].y2,p.step+1});
}else {
q.push(point{ms[tc].x1,ms[tc].y1,p.step+1});
}
}
}
return 0;
}