[洛谷题解] P1979 华容道

纯属玄学做法,要学正解的请跳过这篇

有一次集训模拟赛,直接拿了NOIp原题卷当试卷。我看到这道题,就打了个纯BFS暴力,交洛谷60分,结果真正评测的时候我以最后一个点1.000s的时间获得了100分的好成绩。

于是我意识到这可以是一道卡常练习题。所谓卡常,就是通过优化复杂度中的常数因子使原本超出时间或空间限制(本题是时间)的算法能通过。

普通暴力

我们可以考虑在搜索时用下面的的结构来存储状态:

struct Status{
    int ex,ey,sx,sy;
    // ex,ey是空格的位置,sx,sy是当前绿色棋子的位置。
    signed step;
    // 记录步骤数
    inline signed toInt() {
        return (ex<<15)|(ey<<10)|(sx<<5)|sy;
    }
    // 使用这个toInt函数,可以将当前状态转化为一个整数,这样就可以使用一个数组来判重。
    // 由于n和m只有30,显然用32做进制非常好。不难证明只需一个1048576大小的数组
}

搜索时我们枚举空白格子周边的4个格子,并考虑将空白格子移动到这4个格子(即,将这个棋子移到空白格子中)。

如果枚举到的周边的格子坐标是(sx,sy),那么要交换sx和exsy和ey。否则只需移动exey即可。

然后bfs就很容易写出来了。这是我们最初的纯暴力版本。

#include<bits/stdc++.h>
using namespace std;

int n,m,q;
int a[31][31];

struct Status{
    int ex,ey,sx,sy;
    int step;
    Status() {
    }
    Status(int _ex,int _ey,int _sx,int _sy):
        ex(_ex),ey(_ey),sx(_sx),sy(_sy)
    {

    }

    int toInt() {
        return
            ex*31*31*31+
            ey*31*31+
            sx*31+
            sy;
    }
}que[810010]; //数组模拟队列
int tx,ty;
int h,t; //首尾下标
bool vis[1048576];

//定义“相邻的4个格子”相对当前格子的位置
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int bfs() {
    while(h<t) {
        h++;
        if(que[h].sx==tx && que[h].sy==ty) {
            return que[h].step;
        }
        for(int i=0;i<4;i++) {
            int ex2=que[h].ex+dx[i];
            int ey2=que[h].ey+dy[i];
            if(ex2<1 || ex2>n || ey2<1 || ey2>m) continue;
            if(a[ex2][ey2]==0) continue;
            Status tmp;
            tmp.ex=ex2;
            tmp.ey=ey2;
            tmp.sx=que[h].sx;
            tmp.sy=que[h].sy;
            tmp.step=que[h].step+1;
            if(ex2==que[h].sx && ey2==que[h].sy) {
                tmp.sx=que[h].ex;
                tmp.sy=que[h].ey;
            }
            if(vis[tmp.toInt()]) continue;
            vis[tmp.toInt()]=1;
            t++;
            que[t]=tmp;
            if(que[t].sx==tx && que[t].sy==ty) {
                return que[t].step;
            }
        }
    }
    return -1;
}

int main() {
    //freopen("puzzle.in","r",stdin);
    //freopen("puzzle.out","w",stdout);

    scanf("%d%d%d",&n,&m,&q);

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>a[i][j];
        }
    }

    for(int i=1;i<=q;i++) {
        scanf("%d%d%d%d%d%d",
            &que[1].ex,&que[1].ey,&que[1].sx,&que[1].sy,
            &tx,&ty);
        que[1].step=0;
        h=0;
        t=1;
        for(int i=0;i<=1048575;i++) {
            vis[i]=0;
        }
        printf("%d\n",bfs());
    }
}

这个程序能够获得60分的成绩。

很容易发现,进行一次bfs的时间复杂度为O(n^2m^2),因为最多有n^2m^2种状态,此时最坏时间复杂度为30^4,即810000。再乘上q=500,就是4,0500,0000‬。再加上bfs有较大的常数,不死就怪。

但是显然4,0500,0000‬是跑不满的,因此只需优化一下常数,就能获得更好的成绩。

进行常数优化

仔细观察程序,不难发现,很多地方可以优化常数。

手动O3+Ofast

%:pragma GCC optimize("inline,Ofast",3)
或
#pragma GCC optimize("inline,Ofast",3)

一定要加载头文件前面!

避免初始化清空vis数组

显然vis数组很大,清空浪费时间。

我们考虑维护当前在进行第几次BFS。如果vis数组中的值等于当前次数,才认为这个状态出现过。同样,标记vis时标记为当前次数。

这样就可以不清空vis数组。

使用快读快写。

inline void read(int &ret) {
    ret=0;
    register char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) {ret=ret*10+(c-'0');c=getchar();}
}

void __write(signed x) {
    if(!x) return;
    __write(x/10);
    putchar('0'+x%10);
}

inline void write(const signed &x,char e='\0') {
    if(x>0) __write(x);
    else if(x==0) putchar('0');
    else {putchar('-');__write(-x);}
    if(e) putchar(e);
}

主程序中:
read(n);read(m);read(q);
write(bfs(),'\n');
等等...

使用指针来完成队列操作

实际上,指针比数组下标访问更快。假设有一个int数组arr,那么我们可以定义一个指针int *ptr = arr,此时ptr指向arr[0]ptr+1指向arr[1],以此类推。

取值:
cout<<(*ptr)<<endl;

赋值:
(*ptr) = 25

假设ptr指向的是Status类型,对其step赋值和取值
ptr->size = 12
cout<<(ptr->size)<<endl

我们可以将队列的首尾下标变成首尾指针。那么我们仍然可以使用++h++t这种方式进行队列模拟。

加register, inline

inline可以用在非递归函数的类型前,防止不必要的进栈操作。

register可以用在局部变量的类型前,这样可以定义将变量存在寄存器中,加快访问速度。但是寄存器容量小,不宜使用太多register,否则系统会花时间将较早定义的元素扔出寄存器,放入内存,造成负优化。

修改dx, dy数组,防止搜索时单步回退

我们注意到,BFS扩展(转移)部分常数较大

int dx[4]={0,1,-1,0};
int dy[4]={-1,0,0,1};

这样定义的dx,dy有个性质,即,dx和dy中分别取下标相加等于3的两个元素,相加必等于0。

我们可以给Status结构添加一个属性tp,即,上次使用的dx和dy中的哪个元素。

下一次扩展时,若枚举的i与上次的tp相加得3,说明这样扩展必将退回到上一个状态。显然这个状态是没用的(判重时会continue掉)

对于初始化,只需初始化tp=-1即可(因为没有任何i会与-1相加为3)

最后的代码长这样

// status: [status_undefined]
// oj:     [luogu]
%:pragma GCC optimize("inline,Ofast",3)
#include<stdio.h>
#include<ctype.h>
#define int short // short卡常

int n,m,q;
int a[31][31];

struct Status{
    int ex,ey,sx,sy;
    signed step; // 步骤数等地方不可以使用short,可能会爆
    int tp;
    inline signed toInt() { 
        return (ex<<15)|(ey<<10)|(sx<<5)|sy;
    }
}que[810010];
int tx,ty;
Status *h,*t; //用指针
int vis[1048576];
int vis_t=0;

int dx[4]={0,1,-1,0};
int dy[4]={-1,0,0,1};

inline signed bfs() {
    ++vis_t;
    while(h!=t) {
        ++h;
        if(h->sx==tx && h->sy==ty) {
            return h->step;
        }
        for(register int i=0;i<4;i++) {
            if(i+h->tp==3) continue; //相加等于3的优化
            register int ex2=h->ex+dx[i];
            register int ey2=h->ey+dy[i];
            if(ex2<1 || ex2>n || ey2<1 || ey2>m) continue;
            if(!a[ex2][ey2]) continue;
            ++t;
            t->ex=ex2;
            t->ey=ey2;
            t->sx=h->sx;
            t->sy=h->sy;
            if(ex2==h->sx && ey2==h->sy) {
                t->sx=h->ex;
                t->sy=h->ey;
            }
            register signed _t=t->toInt();
            if(vis[_t]==vis_t) {--t;continue;}
            t->step=h->step+1;
            t->tp=i;
            vis[_t]=vis_t;
            if(t->sx==tx && t->sy==ty) {
                return t->step;
            }
        }
    }
    return -1;
}

inline void read(int &ret) {
    ret=0;
    register char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) {ret=ret*10+(c-'0');c=getchar();}
}

void __write(signed x) {
    if(!x) return;
    __write(x/10);
    putchar('0'+x%10);
}

inline void write(const signed &x,char e='\0') {
    if(x>0) __write(x);
    else if(x==0) putchar('0');
    else {putchar('-');__write(-x);}
    if(e) putchar(e);
}

signed main() {
    read(n);read(m);read(q);

    for(int i=1;i<=n;i++) {
        register int *tt = a[i];
        for(int j=1;j<=m;j++) {
            ++tt;
            read(*tt);
        }
    }

    t=que+1;
    t->tp = -1;
    t->step = 0; // 无需每次初始化的东西放到循环外
    for(register int i=1;i<=q;i++) {
        h=que;
        t=que+1;
        read(t->ex);read(t->ey);read(t->sx);read(t->sy);
        read(tx);read(ty);
        write(bfs(),'\n');
    }
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注