给一个 $n* m$ （$n,m<=1000$）的棋盘，每个位置是 . 或 * 。

. 表示是空地，* 表示是墙，S 表示一开始你在的位置，T 是你的目的地（S 和 T 也是空地）。

每次你可以朝上下左右的一个方向移动一格，前提是没有走出地图边界并且移动到的目标不是墙，每走一步需要 个单位时间。

问走到目的地最少需要多少个单位时间？

我的代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
const int inf=0x3f3f3f3f;
struct Edge{
	int w,to,next;
}e[maxn*maxn];
struct qnode{
	int id,val;
	qnode(int d,int v){
		id=d; val=v;
	}
	friend bool operator<(qnode q1,qnode q2){
		return q1.val>q2.val;
	}
};
int n,m,k,t,vis[maxn*maxn],dis[maxn*maxn],head[maxn*maxn];
char c[maxn][maxn];
void adde(int u,int v,int w){
	e[++k].to=v; e[k].w=w;
	e[k].next=head[u]; head[u]=k;
}
void dijkstra(int s){
	priority_queue<qnode>q;
	for(int i=1;i<=n*m;i++) dis[i]=inf;
	memset(vis,false,sizeof(vis));
	dis[s]=0; q.push(qnode(s,0));
	while(!q.empty()){
		qnode qn=q.top(); q.pop();
		if(vis[qn.id]) continue;
		vis[qn.id]=true;
		for(int i=head[qn.id];i;i=e[i].next){
			int v=e[i].to;
			if(dis[v]>dis[qn.id]+e[i].w){
				dis[v]=dis[qn.id]+e[i].w;
				q.push(qnode(v,dis[v]));
			}
		}
	}
	if(dis[t]==inf) printf("-1\n");
	else printf("%d\n",dis[t]);
}
int main()
{
	int s;
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>c[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i][j]=='*') continue;
			if(i<n && j<m){
				if(c[i][j+1]!='*'){
					adde((i-1)*n+j,(i-1)*n+j+1,1); adde((i-1)*n+j+1,(i-1)*n+j,1);
				}
				if(c[i+1][j]!='*'){
					adde((i-1)*n+j,i*n+j,1); adde(i*n+j,(i-1)*n+j,1);
				}
			} else if(i<n && j==m){
				if(c[i+1][j]!='*'){
					adde((i-1)*n+j,i*n+j,1); adde(i*n+j,(i-1)*n+j,1);
				}
			} else if(i==n && j<m){
				if(c[i][j+1]!='*'){
					adde((i-1)*n+j,(i-1)*n+j+1,1); adde((i-1)*n+j+1,(i-1)*n+j,1);
				}
			}
			if(c[i][j]=='S') s=(i-1)*n+j;
			if(c[i][j]=='T') t=(i-1)*n+j;
		}
	}
	dijkstra(s);
	return 0;
}

代码有亿点点答辩，请见谅