C++(g++ 7.5.0) 解法, 执行用时: 72ms, 内存消耗: 9344K, 提交时间: 2022-08-10 14:25:01

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<map>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,k,sx,sy,tx,ty;
char ditu[1005][1005];
int vis[1005][1005],tp[1005][1005];
int dir[4][2]={0,1,1,0,0,-1,-1,0};
map<pair<int,int>,pair<int,int> >ma;
queue<pair<int,int>> q;
void bfs(){
    q.push(pair<int,int>(sx,sy));
    vis[sx][sy]=0;
    while(!q.empty()){
        pair<int,int> tmp=q.front();q.pop();
        int x=tmp.first,y=tmp.second;
        for(int i=0;i<4;i++){
            int xx=x+dir[i][0],yy=y+dir[i][1];
            if(xx>0&&xx<=n&&yy>0&&yy<=m&&ditu[xx][yy]!='#'&&vis[xx][yy]>vis[x][y]+1){
                vis[xx][yy]=vis[x][y]+1;
                q.push(pair<int,int>(xx,yy));
            }
        }
        if(tp[x][y]){
            int xx=ma[pair<int,int>(x,y)].first,yy=ma[pair<int,int>(x,y)].second;
                if(vis[xx][yy]>vis[x][y]){
                    vis[xx][yy]=vis[x][y];
                    q.push(pair<int,int>(xx,yy));
                }
        }
    }

    if(vis[tx][ty]==INF)cout<<"-1"<<endl;
    else if(vis[tx][ty]==0)cout<<"0"<<endl;
    else cout<<vis[tx][ty]+((vis[tx][ty]-1)/8 )<<endl;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ditu[i][j];
            if(ditu[i][j]=='T'){
                tx=i,ty=j;
            }
            if(ditu[i][j]=='S'){
                sx=i,sy=j;
            }
        }
    }
    memset(vis,INF,sizeof(vis));
    memset(tp,0,sizeof(tp));
    cin>>k;
    for(int i=0;i<k;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        tp[a][b]=tp[c][d]=1;
        ma[pair<int,int>(a,b)]=pair<int,int>(c,d);
        ma[pair<int,int>(c,d)]=pair<int,int>(a,b);
    }
    bfs();
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 5252K, 提交时间: 2019-12-17 19:26:45

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1005;
const int MOD = 1e9+7;
char mp[MAXN][MAXN];
map<pair<int,int>,pair<int,int> > v;
struct node{ int x,y,step; };
int vis[MAXN][MAXN],n,m,stx,sty;
int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
inline bool check(int x,int y){
    if(x<1 || x>n || y<1 || y>m || mp[x][y]=='#' || vis[x][y]) return false;
    return true;
}
inline int bfs(int sx,int sy){
    queue<node> que;
    que.push({sx,sy,0}); vis[sx][sy]=1;
    while(!que.empty()){
        node u=que.front(); que.pop();
        if(mp[u.x][u.y]=='T') return u.step;
        if(v.count({u.x,u.y})){
            int x=v[{u.x,u.y}].first,y=v[{u.x,u.y}].second;
            if(check(x,y)){
                vis[x][y]=1; que.push({x,y,u.step});
            }
        }
        for(int i=0;i<4;i++){
            int xx=u.x+dir[i][0],yy=u.y+dir[i][1];
            if(check(xx,yy)){
                vis[xx][yy]=1;
                if((u.step+1)%9==0) que.push({xx,yy,u.step+2});
                else que.push({xx,yy,u.step+1});
            }
        }
    }
    return -1;
}
int main(){
    //freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]=='S')
                stx=i,sty=j;
    int k; scanf("%d",&k);
    for(int i=1;i<=k;i++){
        int x,y,xx,yy; scanf("%d%d%d%d",&x,&y,&xx,&yy);
        v[{x,y}]={xx,yy};
        v[{xx,yy}]={x,y};
    }
    printf("%d\n",bfs(stx,sty));
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 76ms, 内存消耗: 5480K, 提交时间: 2019-12-15 14:24:53

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int INF=0x3f3f3f3f;
char s[N][N];
int n,m,k,S,E;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int d[N*N];
unordered_map<int,int> ma;
int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",s[i]);
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(s[i][j]=='S') S=i*m+j;
            if(s[i][j]=='T') E=i*m+j;
        }
    }
    scanf("%d",&k);
    for(int i=0,x1,x2,y1,y2;i<k;i++) {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1--,x2--,y1--,y2--;
        ma[x1*m+y1]=x2*m+y2;
        ma[x2*m+y2]=x1*m+y1;
    }
    memset(d,INF,sizeof d);
    queue<int> qu;
    qu.push(S),d[S]=0;
    while(!qu.empty()) {
        int u=qu.front();qu.pop();
        for(int i=0;i<4;i++) {
            int x=u/m+dx[i],y=u%m+dy[i];
            if(x<0||x>=n||y<0||y>=m||s[x][y]=='#') continue;
            if(d[x*m+y]>d[u]+1) {
                d[x*m+y]=d[u]+1;
                qu.push(x*m+y);
            }
        }
        if(ma.count(u)) {
            if(d[ma[u]]>d[u]) {
                d[ma[u]]=d[u];
                qu.push(ma[u]);
            }
        }
    }
    if(d[E]==INF) printf("-1\n");
    else printf("%d\n",d[E]+(d[E]-1)/8);
    return 0;
}