K 迷宫题解_牛客博客

$description:$
有一个 $n\times m$ 的矩阵 $,$ 每次可以往上 $/$ 下 $/$ 左 $/$ 右移动一格 $.$

你还可以最多进行一次跳跃 $,$ 如果 $|x1-x2|<=d$ 并且 $|y1-y2|<=d,$ 那么可以从 $(x1,y1)$ 跳跃到 $(x2,y2).$

求出最小的操作次数 $,$ 并给出一种方案 $.$

$solution:$

首先 $,$ 如果我们不使用跳跃 $,$ 那么直接 $O(nm)BFS$ 即可。

记 $disS[x][y]$ 和 $disT[x][y]$ 分别表示 $(x,y)$ 到起点 $/$ 终点的距离 $,$ 如果没有路径则其值为 $INF.$

如果进行跳跃 $,$ 设我从 $(x1,y1)$ 跳到 $(x2,y2),$ 那么这种方案的 $ans$ 为 $1 + disS[x1][y1] + disT[x2][y2].$

那么我们需要对于每个 $S$ 能走到的点 $,$ 对 $disT[][]$ 进行一次矩阵查询最小值 $.$

可以使用单调队列来解决 $,$ 具体方法是先在 $x$ 轴上做一遍滑动窗口 $,$ 再把求出的答案在 $y$ 轴上再做一遍滑动窗口 $.$

然而我赛时写的是一个 $kd-tree.$

用 $kd-tree$ 来优化查询 $,$ 复杂度下界是 $O(nm),$ 具体效率看数据强度和剪枝强度 $.$

目前经过多次调参和加火车头只能通过 $96.67%$ 的数据 $.$

~~有没有人写个kdtree暴力过去啊，标算太trival了，没意思~~

$code(kdtree$ 解法 $):$

//96.67%
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline int Get(){
    static char ch; ch = getchar();
    while (ch!='.'&&ch!='X'&&ch!='S'&&ch!='T')ch=getchar();
    return ch;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int N = 2005,V = 2005 * 2005,INF = 5000 * 5000 + 5;
int n,m,K; char mp[N][N];
inline bool in(int x,int y){ return 0<=x&&x<n&&0<=y&&y<m; } 
struct Point{
    int x,y;
    bool in(){ return 0<=x&&x<n&&0<=y&&y<m; } 
    Point(int xx=0,int yy=0){ x=xx,y=yy; }
}s,t,ps[V],pt[V]; int ls,lt;
Point Q[V]; int ql,qr;
const int txy[] = {1,0,-1,0,1};
int dis[N][N],dit[N][N]; Point lss[N][N],lst[N][N];
inline void Bfs1(){
    register int i,j; Point A,B;
    Q[ql=qr=1] = ps[ls=1] = s; dis[s.x][s.y] = 1;
    while (ql <= qr){
        A = Q[ql],++ql;
        for (i = 0; i < 4; ++i){
            B = A,B.x += txy[i],B.y += txy[i+1];
            if (B.in() && !dis[B.x][B.y] && mp[B.x][B.y] != 'X'){
                dis[B.x][B.y] = dis[A.x][A.y] + 1,lss[B.x][B.y] = A;
                Q[++qr] = B,ps[++ls] = B;
            }
        }
    }
    Q[ql=qr=1] = pt[lt=1] = t; dit[t.x][t.y] = 1;
    while (ql <= qr){
        A = Q[ql],++ql;
        for (i = 0; i < 4; ++i){
            B = A,B.x += txy[i],B.y += txy[i+1];
            if (B.in() && !dit[B.x][B.y] && mp[B.x][B.y] != 'X'){
                dit[B.x][B.y] = dit[A.x][A.y] + 1,lst[B.x][B.y] = A;
                Q[++qr] = B,pt[++lt] = B; 
            }
        }
    }
    for (i = 0; i < n; ++i) for (j = 0; j < m; ++j){
        if (!dis[i][j]) dis[i][j] = INF;
        if (!dit[i][j]) dit[i][j] = INF;
    }
}
inline bool cmpx(Point A,Point B){ return A.x < B.x; }
inline bool cmpy(Point A,Point B){ return A.y < B.y; }
inline bool cmpd(Point A,Point B){ return dit[A.x][A.y] <= dit[B.x][B.y]; }
inline Point Mn(Point A,Point B){ return cmpd(A,B) ? A : B; }
Point A[V],P[V];
int lc[V],rc[V],mxx[V],mxy[V],mnx[V],mny[V],cnto; Point mnd[V];
int Build(int l,int r,int d){
    if (l > r) return 0;
    int o = ++cnto,mid = l + r >> 1;
    if (d) nth_element(A+l,A+mid,A+r+1,cmpy); else nth_element(A+l,A+mid,A+r+1,cmpx);
    mnd[o] = P[o] = A[mid];
    mxx[o] = mnx[o] = A[mid].x;
    mxy[o] = mny[o] = A[mid].y;
    if (lc[o] = Build(l,mid-1,d^1)){
        mxx[o] = max(mxx[o],mxx[lc[o]]),mxy[o] = max(mxy[o],mxy[lc[o]]);
        mnx[o] = min(mnx[o],mnx[lc[o]]),mny[o] = min(mny[o],mny[lc[o]]);
        mnd[o] = Mn(mnd[o],mnd[lc[o]]);
    }
    if (rc[o] = Build(mid+1,r,d^1)){
        mxx[o] = max(mxx[o],mxx[rc[o]]),mxy[o] = max(mxy[o],mxy[rc[o]]);
        mnx[o] = min(mnx[o],mnx[rc[o]]),mny[o] = min(mny[o],mny[rc[o]]);
        mnd[o] = Mn(mnd[o],mnd[rc[o]]);
    }
    return o;
}
int ans; Point qans,anss,anst;
int qxl,qxr,qyl,qyr,vvv;
inline void Ask(int o){
    if (cmpd(qans,mnd[o]) || dit[mnd[o].x][mnd[o].y] + vvv >= ans || qxr < mnx[o] || qxl > mxx[o] || qyl > mxy[o] || qyr < mny[o]) return;
    if (qxl <= mnx[o] && mxx[o] <= qxr && qyl <= mny[o] && mxy[o] <= qyr){
        qans = Mn(qans,mnd[o]); return;
    }
    if (qxl <= P[o].x && P[o].x <= qxr && P[o].y >= qyl && P[o].y <= qyr) qans = Mn(qans,P[o]);
    if (lc[o]) Ask(lc[o]); if (rc[o]) Ask(rc[o]);
}
Point Ans[V]; int la;
inline void Print(){
    write(la-1),putchar('\n');
    for (register int i = 1; i <= la; ++i) write(Ans[i].x),putchar(' '),write(Ans[i].y),putchar('\n');
}
inline void Getans1(){
    Point A;
    if (dis[t.x][t.y] >= INF){ puts("-1"); return; }
    Ans[la=1] = s;
    while (Ans[la].x != t.x || Ans[la].y != t.y) Ans[la+1] = lst[Ans[la].x][Ans[la].y],++la;
    Print();
}
#define MOD 32
#define W 1
#define LIMIT 10000
#define LIMIT2 100000
inline void solve2(){
    register int i,j,v;
    swap(lt,ls); swap(pt,ps); swap(s,t);
    for (i = 0; i < n; ++i) for (j = 0; j < m; ++j)
        swap(dis[i][j],dit[i][j]),swap(lss[i][j],lst[i][j]);
    ans = INF,anss = anst = Point(-1,-1);
    for (i = 1; i <= lt; ++i) A[i] = pt[i];
    Build(1,lt,1);
//    random_shuffle(ps+1,ps+ls+1);
    int TOT = 0;
    for (i = 1; i <= ls; ++i) if (ls<=LIMIT||i%MOD<=W){
        qxl = ps[i].x - K,qxr = ps[i].x + K;
        qyl = ps[i].y - K,qyr = ps[i].y + K;
        qxl = max(qxl,0),qyl = max(qyl,0),qxr = min(qxr,n-1),qyr = min(qyr,m-1);
        vvv = dis[ps[i].x][ps[i].y] + 1,qans = ps[i],Ask(1);
        v = dit[qans.x][qans.y] + dis[ps[i].x][ps[i].y] + 1;
        if (v < ans) ans = v,anss = ps[i],anst = qans;
        ++TOT;
        if (TOT>=LIMIT2&&ans>=INF){
            puts("-1"); return;
        }
    }
    if (ans >= INF){ puts("-1"); return;  }
    Ans[la=1] = anss;
    while (Ans[la].x != s.x || Ans[la].y != s.y) Ans[1+la] = lss[Ans[la].x][Ans[la].y],++la;
    reverse(Ans+1,Ans+la+1); Ans[++la] = anst;
    while (Ans[la].x != t.x || Ans[la].y != t.y) Ans[1+la] = lst[Ans[la].x][Ans[la].y],++la;
    reverse(Ans+1,Ans+la+1);
    Print();
}

int main(){
    register int i,j,v; //srand(time(NULL));
    read(n),read(m),read(K);
    for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) mp[i][j] = Get();
    for (i = 0; i < n; ++i) for (j = 0; j < m; ++j)
        if (mp[i][j] == 'S') s = Point(i,j); else if (mp[i][j] == 'T') t = Point(i,j);
    Bfs1();
    if (!K){ Getans1(); return 0; }
    bool flag = 0;
    if (lt < ls){
        solve2(); return 0;
    }
    ans = INF,anss = anst = Point(-1,-1);
    for (i = 1; i <= lt; ++i) A[i] = pt[i];
    Build(1,lt,1);
//    random_shuffle(ps+1,ps+ls+1);
    int TOT = 0;
    for (i = 1; i <= ls; ++i) if (ls<=LIMIT||i%MOD<=W){
        qxl = ps[i].x - K,qxr = ps[i].x + K;
        qyl = ps[i].y - K,qyr = ps[i].y + K;
        qxl = max(qxl,0),qyl = max(qyl,0),qxr = min(qxr,n-1),qyr = min(qyr,m-1);
        vvv = dis[ps[i].x][ps[i].y] + 1,qans = ps[i],Ask(1);
        v = dit[qans.x][qans.y] + dis[ps[i].x][ps[i].y] + 1;
        if (v < ans) ans = v,anss = ps[i],anst = qans;
        ++TOT;
        if (TOT>=LIMIT2&&ans>=INF){
            puts("-1"); return 0;
        }
    }
    if (ans >= INF){ puts("-1"); return 0;  }
    Ans[la=1] = anss;
    while (Ans[la].x != s.x || Ans[la].y != s.y) Ans[1+la] = lss[Ans[la].x][Ans[la].y],++la;
    reverse(Ans+1,Ans+la+1); Ans[++la] = anst;
    while (Ans[la].x != t.x || Ans[la].y != t.y) Ans[1+la] = lst[Ans[la].x][Ans[la].y],++la;
    Print();
    return 0;
}

K 迷宫 题解

K 迷宫题解