纯属玄学做法，要学正解的请跳过这篇
有一次集训模拟赛，直接拿了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和ex，sy和ey。否则只需移动ex和ey即可。
然后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');
}
}
Comments | NOTHING