迷宫

先跑出起点到每个点的最短路，然后每个点到终点的最短路。

如果d==0，那么直接特判，否则使用一定是最优的。

枚举每个点，到能到的最小到终点的最短路，其实就是矩形查询min。

直接ST表维护即可。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2010,inf=0x3f3f3f3f;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int vis[N][N][2],sx,sy,ex,ey,n,m,d,res=inf,a[10];    char g[N][N];
pair<int,int> pre[N][N][2];
vector<pair<int,int> > ans;
int st[N][N][14];
void init_st(){
    int i, j, k;
    for(k = 1; k <=12; ++k)
        for(i = 1; i <= n-(1<<k)+1; ++i)
        for(j = 1; j <= m-(1<<k)+1; ++j){
            int t1 = min(st[i][j][k-1], st[i+(1<<(k-1))][j][k-1]);
            int t2 = min(st[i][j+(1<<(k-1))][k-1], st[i+(1<<(k-1))][j+(1<<(k-1))][k-1]);
            st[i][j][k] = min(t1, t2);
        }
}
int ask(int x1, int y1, int x2, int y2){
    int k1 = log2(x2-x1+1);
    int k2 = log2(y2-y1+1);
    if(k1==k2) return min(st[x1][y1][k1],min(st[x2-(1<<k1)+1][y1][k1],
    min(st[x1][y2-(1<<k2)+1][k1], st[x2-(1<<k1)+1][y2-(1<<k2)+1][k1])));
    if(k1<k2){
        int k = k1;
        int minret = 0x3f3f3f3f;
        for(int i = y1; i <= y2 - (1<<k) + 1; i += (1<<k))
            minret = min(minret, min(st[x1][i][k], st[x2-(1<<k)+1][i][k]));
        minret = min(minret, min(st[x1][y2-(1<<k)+1][k], st[x2-(1<<k)+1][y2-(1<<k)+1][k]));
        return minret;
    }
    int k = k2;
    int minret = 0x3f3f3f3f;
    for(int i = x1; i <= x2-(1<<k)+1; i += (1<<k))
        minret = min(minret, min(st[i][y1][k], st[i][y2-(1<<k)+1][k]));
    minret = min(minret, min(st[x2-(1<<k)+1][y1][k], st[x2-(1<<k)+1][y2-(1<<k)+1][k]));
    return minret;
}
void bfs(int sx,int sy,int k){
    queue<pair<int,int> > q;    q.push({sx,sy});    vis[sx][sy][k]=0;
    while(q.size()){
        int x=q.front().first,y=q.front().second;    q.pop();
        for(int i=0;i<4;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&g[tx][ty]!='X'&&vis[tx][ty][k]==inf){
                vis[tx][ty][k]=vis[x][y][k]+1,q.push({tx,ty});
                pre[tx][ty][k]={x,y};
            }            
        }
    }
}
void dfs(int x,int y){
    if(!x||!y)    return ;
    if(pre[x][y][0].first)    dfs(pre[x][y][0].first,pre[x][y][0].second);
    ans.push_back({x,y});
}
void dfs1(int x,int y){
    if(!x||!y)    return ;
    ans.push_back({x,y});
    if(pre[x][y][1].first)    dfs1(pre[x][y][1].first,pre[x][y][1].second);
}
signed main(){
    cin>>n>>m>>d;    memset(vis,0x3f,sizeof vis);
    for(int i=1;i<=n;i++)    scanf("%s",g[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='S')    sx=i,sy=j;
            if(g[i][j]=='T')    ex=i,ey=j;
        }
    }
    bfs(sx,sy,0),bfs(ex,ey,1);
    if(d==0){
        if(vis[ex][ey][0]==inf)    return puts("-1"),0;
        dfs(ex,ey);    cout<<vis[ex][ey][0]<<endl;
        for(auto s:ans)    printf("%d %d\n",s.first-1,s.second-1);
        return 0;
    }
    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    st[i][j][0]=vis[i][j][1];
    init_st();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int ak=vis[i][j][0]+1+ask(max(1,i-d),max(1,j-d),min(n,i+d),min(m,j+d));
            if(ak<res)    res=ak,a[1]=i,a[2]=j;
        }
    }
    if(res==inf)    return puts("-1"),0;
    dfs(a[1],a[2]);    int po=res-vis[a[1]][a[2]][0]-1;
    for(int i=max(1,a[1]-d);i<=min(n,a[1]+d);i++){
        for(int j=max(1,a[2]-d);j<=min(m,a[2]+d);j++){
            if(vis[i][j][1]==po){
                dfs1(i,j);
                cout<<res<<endl;
                for(auto s:ans)    printf("%d %d\n",s.first-1,s.second-1);
                return 0;
            }
        }
    }
    return 0;
}