立体推箱子2【AcWing192】题解
chinaxjh
2019-10-05 07:59:13
### 前言
果然是$AcWing$中的困难难度题，花了我2个小时的时间才做出来，期间也看过另一篇题解，与我一开始的思路吻合，于是尝试了一下，花了一个小时，码了好几$KB$，第一次错了，发现有很大问题，于是推翻又码了好几$KB$,又发现了错误，然后感觉我的思路从根本上是有问题的，于是就放弃了这个思路，开始找规律......（此处省略无数次的失败提交和辛酸经历），终于解决了这道题，简直令我感动到眼泪流下来。
### 题目描述
题意还是挺明确的，至少我没有感觉到歧义，所以大略地讲一下：
在一个平面上有一个箱子，箱子有竖立，平行于x轴或平行于y轴几种可能，可以选择上下左右移动，然后同时箱子的位置会改变，状态可能会改变，给出起点和终点，要你求最少的步数。
----------
### 算法1
##### 宽搜 接近$O(xy)$
从起点开始宽搜，然后开一个$f[ch,i,j]$数组记录在ch状态下($U$,$V$,$H$)到达坐标$(x,y)$的最小步数，初始赋值为无限大，在宽搜过程中发现比原有答案小就入队，反复迭代优化，但基本上不会多次迭代（当然也有例外，要不然$SPFA$就不会死了），但面对如此大的数据范围，这种算法时间和空间肯定是都会超出限制的，但可以用来对拍，找规律（此题正解之一），所以也是很重要的。（多亏我先打了这个代码）
#### 时间&空间复杂度
接近$O(xy)$
#### Pascal 代码
```
const max=100;min=-100;//定宽搜上线
var
f:array['A'..'Z',-200..200,-200..200] of longint;
a:array[0..10000000] of char;
b,x,y:array[0..10000000] of longint;
ch1,ch:char; xx,yy,xxx,yyy,i,l,r:longint;
begin
readln(ch1,xx,yy);
fillchar(f,sizeof(f),63);//初始赋一个极大值，类似于memset
l:=1; r:=1; a[1]:=ch1; b[1]:=0; x[1]:=xx; y[1]:=yy;
f[ch1,xx,yy]:=0;//初始化宽搜队列，头尾指针和起点步数
while l<=r do
begin
for i:=1 to 4 do//分别对应上下左右四个方向
begin
xxx:=x[l];
yyy:=y[l];
case i of
1:case a[l] of
'U':begin ch:='H'; yyy:=yyy+1; end;//注意箱子状态的变化，一定要仔细，别写错了，可以拿我的对照一下
'H':begin ch:='U'; yyy:=yyy+2; end;//注意我们定位的方格在箱子中的位置，有时需要+或-2，后面也是一样的
'V':begin ch:='V'; yyy:=yyy+1; end;
end;//向上
2:case a[l] of
'U':begin ch:='H'; yyy:=yyy-2; end;
'H':begin ch:='U'; yyy:=yyy-1; end;
'V':begin ch:='V'; yyy:=yyy-1; end;
end;//向下
3:case a[l] of
'H':begin ch:='H'; xxx:=xxx-1; end;
'V':begin ch:='U'; xxx:=xxx-1; end;
'U':begin ch:='V'; xxx:=xxx-2; end;
end;//向左
4:case a[l] of
'H':begin ch:='H'; xxx:=xxx+1; end;
'V':begin ch:='U'; xxx:=xxx+2; end;
'U':begin ch:='V'; xxx:=xxx+1; end;
end;//向右
end;
if (xxx>=min) and (yyy>=min) and (xxx<=max) and (yyy<=max) then//如果没有超出上限
begin
if b[l]+1<f[ch,xxx,yyy] then//并且答案更优
begin
f[ch,xxx,yyy]:=b[l]+1;
inc(r);
a[r]:=ch;
b[r]:=b[l]+1;
x[r]:=xxx;
y[r]:=yyy;//更新答案+入宽搜队列
end;
end;
end;
inc(l);
end;
write(f['U',0,0]:3);//输出答案，带3个场宽，后面打表找规律时表格更整齐，规律可以好找不少
end.
```
麻烦诸位$C++$巨佬不要吐槽，我才刚来$AcWing$，我会把注释写的尽量明白的（虽然不写也看得懂）
----------
### 算法2
##### (找规律/数学) $O(1)$
我想到的第二个思路，本来抱着试试看的心态，结果成为了我$A$掉这道题的方法
我们用之前贴出的代码在小数据中找一下规律，如下面三张图片
箱子状态为U 坐标x为0~24 y为0~24的答案
箱子状态为H 坐标x为0~24 y为0~24的答案
箱子状态为V 坐标x为0~24 y为0~24的答案
感觉好像有规律的样子，让我们先来分析为U情况下的规律
红线竖向标出，每三位一节连续自然数，但是从横向红线可以看出，只有在横向三位一节每节的最后一列，这样的循环是从第一个开始的，其他的都是从第4个开始的，同时最上面一行的数也有很明显规律，同样3位一节去寻找，这里就不列举具体公式了，可以自己推，也可以看我的代码
你以为这样就结束了......又不然我也不会这么心累了
仔细一看就会发现，前三列和前三行都不满足刚刚我们找出来的规律，所以对于前三行和前三列还要自己分别推出公式（当然也是有技巧的），无非就是三位一节分好之后找等差数列即可
当箱子状态为$H$或$V$的状态同理，但这两个之间是有规律的，可以从上面的图里看出来，行列反一下的答案是一样的(比如$H(1,3)=V(1,3)$)，所以只要找出其中一种状态的公式就可以了。
同时，我们还可以发现所得答案正负是对称的(如$U(1,1)=U(-1,1)$)，这也是很重要的一个规律
#### 时间&空间复杂度
都是$O(1)$
#### C++ 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y,ans;
char ch;
int ansssu(int x,int y)//U状态的情况
{
int ans;
if (x<0) x=-x;
if (y<0) y=-y;//负数取绝对值不影响结果
if (x==0)
{
if (y%3==0) return y/3*2;
else return y/3*2+2+y%3;
}
if (x==1)
{
if (y==0||y==3) return 3;
if (y==1||y==2||y==4) return 6;//前面的好像没有规律，就打一个小表
if (y%3==0) return y/3*2+1;
else return y/3*2+3+y%3;//公式看不懂可以发帖询问，或者私信我，但最好还是自己推一下
}
if (x==2)
{
if (y==0||y==3) return 4;
if (y==1||y==2||y==4) return 6;
if (y%3==0) return y/3*2+2;
else return y/3*2+3+y%3;
}//分别判断x=0,1,2的情况
if (x%3==0) return y/3*2+x/3*2+y%3;
ans=(1+x/3)*2+x%3;
if (y==0) return ans;
else if (y==1||y==2) return ans+1;
else return (y-3)/3*2+y%3+ans;//通用公式
}
int ansssh(int x,int y)//H状态的情况（用V也是可以的），于U的情况基本同理，就不注释了，但x,y必须分清
{
int ans;
if (x<0) x=-x;
if (y<0) y=-y;
if (x>=3&&y>=3)
{
ans=y/3;
ans=ans*2+3;
if (y%3==2) ans++;
return (x/3-1)*2+ans+x%3;
}
if (y==0||y==2)
{
if (x==0) return 4;
if (x==1||x==2) return 5;
return x/3*2+2+x%3;
}
if (y==1)
{
return x/3*2+1+x%3;
}
if (x==0)
{
ans=(y+1)/3*2+2;
if (y%3==1) return ans-3;
if (y%3==2) return ans;
ans=y/3*2+3;
return ans;
}
if (x==1)
{
ans=y/3*2+4;
if (y%3==0) return ans;
if (y%3==1) return ans-2;
return ans+1;
}
if (x==2)
{
ans=y/3*2+4;
if (y%3==0) return ans;
if (y%3==1) return ans-1;
return ans+1;
}
}
int main()
{
while (cin>>ch>>x>>y)
{
ans=0;
if (ch=='U')
{
cout<<ansssu(x,y)<<endl;
}
if (ch=='H')
{
cout<<ansssh(x,y)<<endl;
}
if (ch=='V')
{
cout<<ansssh(y,x)<<endl;//找到相反这一个规律就可以少打不少内容
}
}
}
```
### 后记
这道题代码难度不大，主要侧重于思维，数学功底一定要扎实，这样可以更加轻松，而且一定要注意细节，思路要清楚，避免不必要的调试。
$All$ $in$ $all$还是要继续努力，两小时一道题还是有点慢......