题目： This past fall, Farmer John took the cows to visit a corn maze. But this wasn’t just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide’s start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.
The outside of the corn maze is entirely corn except for a single exit.
The maze can be represented by an N x M (2 <= N <= 300; 2 <= M <= 300) grid. Each grid element contains one of these items:
Corn (corn grid elements are impassable)
Grass (easy to pass through!)
A slide endpoint (which will transport a cow to the other endpoint)
The exit
A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.
Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).
Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the ‘at’ symbol (@). What is the minimum time she needs to move to the exit space? https://www.luogu.com.cn/problem/P1825
题意： @是起点，=是终点，-是可以走的格子，#是不能走的格子，A~Z是传送门，走到这个格子的时候会自动传送到相同字母的格子。每次可以移动到相邻的一格，耗费一秒，从传送门到另一个格子不耗费时间，问走到终点所需的最短时间是多少。
思路： 因为是求最短时间，所以想到bfs。唯一要注意的地方就是传送门不耗费时间，以及传送门只进行单项标记。因为从传送门的一端到另一端，只需要标记开始的那一端走过，出来的那一端不必标记，才能保证结果的准确性。
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 80112002; const inline int read(){ int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 1000010 int n , m; int sx , sy;//起点 int ex , ey;//终点 char a[310][310];//地图 int b[310][310];//0不能走，1能走， int c[30][2][2];//传送门的坐标 bool v[310][310];//1走过，0没走过 int dir[4][4]={{-1,0},{1,0},{0,-1},{0,1}}; int l[310][310];//起点走到各点的时间 int vis[30]={0};//用来记录传送门 int res = 0; void bfs() { queue<int> q[2]; q[0].push(sx); q[1].push(sy); while(!q[0].empty()) { int x = q[0].front(); int y = q[1].front(); q[0].pop(); q[1].pop(); // cout << x << " " << y << endl; for(int i = 0 ; i <= 3 ; i++) { int dx = x + dir[i][0]; int dy = y + dir[i][1]; // cout << dx << " " << dy << endl; if(dx>=1&&dx<=n&&dy>=1&&dy<=m) { if(b[dx][dy]==0) { continue; } else { if(v[dx][dy]==1) continue; else { if(a[dx][dy]=='.') { l[dx][dy] = l[x][y]+1; q[0].push(dx); q[1].push(dy); v[dx][dy] = 1; } else if(a[dx][dy]=='=') { if(l[dx][dy]==-1) l[dx][dy] = l[x][y]+1; else l[dx][dy]=min(l[dx][dy],l[x][y]+1); } else if(b[dx][dy]==2) { v[dx][dy] = 1; if(c[a[dx][dy]-'a'][0][0]==dx&&c[a[dx][dy]-'a'][0][1]==dy) { q[0].push(c[a[dx][dy]-'a'][1][0]); q[1].push(c[a[dx][dy]-'a'][1][1]); l[dx][dy] = l[x][y]+1; l[c[a[dx][dy]-'a'][1][0]][c[a[dx][dy]-'a'][1][1]]=l[dx][dy]; } else if(c[a[dx][dy]-'a'][1][0]==dx&&c[a[dx][dy]-'a'][1][1]==dy) { q[0].push(c[a[dx][dy]-'a'][0][0]); q[1].push(c[a[dx][dy]-'a'][0][1]); l[dx][dy] = l[x][y]+1; l[c[a[dx][dy]-'a'][0][0]][c[a[dx][dy]-'a'][0][1]] = l[dx][dy]; } } } } } } } } int main() { scanf("%d %d",&n,&m); getchar(); for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { l[i][j] = -1; scanf("%c",&a[i][j]); if(a[i][j]=='@') { sx = i; sy = j; v[i][j] = 1; b[i][j] = 1; l[i][j] = 0; } else if(a[i][j]=='=') { ex = i; ey = j; b[i][j] = 1; } else if(a[i][j]=='.') { b[i][j] = 1; } else if(a[i][j]=='#') { b[i][j] = 0; } else { b[i][j] = 2; if(vis[a[i][j]-'a']==0) { c[a[i][j]-'a'][0][0] = i; c[a[i][j]-'a'][0][1] = j; vis[a[i][j]-'a'] = 1; } else { c[a[i][j]-'a'][1][0] = i; c[a[i][j]-'a'][1][1] = j; } } } getchar(); } bfs(); printf("%d\n",l[ex][ey]); return 0; }