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

输入 第1行两个整数N和M； 下面n行，每行M个数（入口点和BOSS点无小怪和传送门），表示地图。地图数据之间无空格。每步只能走一格，方向上下左右。左上角为入口点，右下角为出口点。

输出 一个整数，表示小A最少需要走多少步。如果小A不能走到目标，则输出“No Solution.”。

样例输入 复制 3 4 0000 00A0 A000 样例输出 复制 4 提示

输入 输出 样例说明 样例1 3 4 0000 00A0 A000 4 路线如图8.4-2：即第一步从(1,1)到(2,1)；第二步从(2,1)到(3,1)并马上传送到(2,3)；第三步从(2,3)到(2,4)；第四步从(2,4)到(3,4)。 样例2 4 6 010100 01A100 011101 0000A0 10

(1,1)→(2,1)→(3,1)→(4,1)→(4,2)→(4,3)→(4,4)→(4,5)(2,3)→(1,3)→(2,3)(4,5)→(4,6)

然后，这是代码

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("02")
using namespace std;
const int e[4][2]={-1,0,1,0,0,-1,0,1};
int n,m,i,t,w,sx,sy,fx,fy,sb,fb,f[2010][2010],c[10000010],b[10000010];
char a[2010][2010];
void xz(int x,int y){
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]==a[x][y])
				if(i!=x&&j!=y){sx=i;sy=j;return ;}
}
main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m;
	for(i=1;i<=n;i++) cin>>a[i]+1;
	memset(f,127,sizeof(f));
	t=w=1;b[1]=1;c[1]=1;f[1][1]=0;
	while(t<=w){
		fx=b[t];fy=c[t];fb=f[fx][fy];
		if(fx==n&&fy==m) return cout<<fb,0;
		for(i=0;i<4;i++){
			sx=fx+e[i][0];sy=fy+e[i][1];sb=fb+1;
			if(sx<1||sx>n||sy<1||sy>m) continue;
			if(a[sx][sy]>='A'&&a[sx][sy]<='Z') xz(sx,sy);
			if(a[sx][sy]!='1')
			if(sb<f[sx][sy])w++,b[w]=sx,c[w]=sy,f[sx][sy]=sb;
		}
		t++;
	}
	cout<<"No Solution.";
	return 0;
}