题目描述

小A是个小术士，他很喜欢单挑BOSS。单挑BOSS是指在N×M的矩形(N，M≤100)，上面遍布了小怪和传送门，其中l表示有小怪，O表示无小怪，大写字母表示传送门，传送门是一对相同的大写字母，如遇到一个大写A(第一次必须传送)则马上可以到达另一个大写A的位置（次数不限，但每次进入传送点只传送过去，不会直接传送回来，数据保证每个传送门有且仅有相对应的另一个传送门）。小A在左上方(1，1)出发，BOSS躲在右下方(N，M)。小A绝不会在小怪身上浪费时间（当然是绕开他们），并且想通过传送门尽快到达BOSS身边。

代码

#pragma GCC optimize( 2 )
#include<bits/stdc++.h>
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define dFor(i,j,k) for(int i=j;i>=k;i--)
const int MAXN=101;
using namespace std;
int n,m;
bool vis[MAXN][MAXN];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
char tmap[MAXN][MAXN];
unordered_map<int,int> mpx,mpy;
queue<int> qx,qy,qstep;
void bfs(){
	qx.push(1),qy.push(1),qstep.push(0);
	while(!qx.empty()){
		int prex=qx.front(),prey=qy.front(),prestep=qstep.front();
		qx.pop(),qy.pop(),qstep.pop();
		For(i,0,3){
			int nx=prex+dx[i],ny=prey+dy[i],nstep=prestep+1;
			if(nx<1||ny<1||nx>n||ny>m) continue;
			if(vis[nx][ny]==1) continue;
			if(tmap[nx][ny]=='1') continue;
			if(nx==n&&ny==m){
				cout<<nstep;
				exit(0);
			}
			if(tmap[nx][ny]=='0') vis[nx][ny]=1,qx.push(nx),qy.push(ny),qstep.push(nstep);
			else qx.push(mpx[nx*m+ny]),qy.push(mpy[nx*m+ny]),qstep.push(nstep);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	For(i,1,n)
		For(j,1,m)
			cin>>tmap[i][j];
	For(i,1,n){
		For(j,1,m){
			if(tmap[i][j]>='A'&&tmap[i][j]<='Z'){
				For(ii,1,n){
					For(jj,1,m){
						if(ii==i&&jj==j) continue;
						if(tmap[ii][jj]==tmap[i][j]){
							mpx[i*m+j]=ii,mpy[i*m+j]=jj;
						}
					}
				}
			}
		}
	}
	bfs();
	cout<<"No Solution.";
	return 0;
}