自动搬运

查看原文

来自洛谷，原作者为

	wangyizhi 昨夜西风凋碧树。独上高楼，望尽天涯路。

搬运于2025-08-24 23:11:16，当前版本为作者最后更新于2025-03-17 20:11:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

诈骗题。

就是写起来有点恶心。。。（当然也可能是我的问题。。。）

题目分析

以下记小钢珠的数量为 $k$。

感觉直接不是很能做？看到 $n,m\le 15$，$k\le 3$，果断暴力。

称当前小钢珠的位置和重力方向为一个局面。将每个局面看作一个点，那么两种操作就是点之间的边（废话），且一个点只有两条出边。

显然点数是 $O((nm)^k)$ 的，则边数也是 $O((nm)^k)$ 的。注意到这个数大概在 $10^7\sim 10^8$ ，于是果断 bfs，然后就过了。具体模拟就不说了，实在不行的可以看代码。实测常数很小，不卡常最慢的点也只跑了 15ms。

AC Code

#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
//bool Mst;
const int N=16;
bool mp[N][N];
int nxt[4][N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bitset<100000000> to;
map<int,int> en;
int n,m,k;
struct pt
{
	int x,y;
};
struct node
{
	int dir;
	pt a[3];
	node(pt a0={0,0},pt a1={0,0},pt a2={0,0},int d=0){dir=d,a[0]=a0,a[1]=a1,a[2]=a2;}
	inline int get()
	{
		return dir*N*N*N*N*N*N+a[2].x*N*N*N*N*N+a[2].y*N*N*N*N+a[1].x*N*N*N+a[1].y*N*N+a[0].x*N+a[0].y;
	}
	inline void tagall()
	{
		to[node(a[0],a[1],a[2],dir).get()]=1;
		to[node(a[0],a[2],a[1],dir).get()]=1;
		to[node(a[1],a[0],a[2],dir).get()]=1;
		to[node(a[1],a[2],a[0],dir).get()]=1;
		to[node(a[2],a[0],a[1],dir).get()]=1;
		to[node(a[2],a[1],a[0],dir).get()]=1;
	}
};
inline node turn(node nd,int op)
{
	nd.dir=(nd.dir+op+4)%4;
	for(int i=0;i<k;i++) if(nd.a[i].x<n&&nd.a[i].y<m)
	{
		if(nd.dir&1) nd.a[i]={nd.a[i].x,nxt[nd.dir][nd.a[i].x][nd.a[i].y]-dy[nd.dir]};
		else nd.a[i]={nxt[nd.dir][nd.a[i].x][nd.a[i].y]-dx[nd.dir],nd.a[i].y};
	}
	int tmp[N][N];
	memset(tmp,0,sizeof(tmp));
	for(int i=0;i<k;i++)
	{
		if(nd.a[i].x<0||nd.a[i].y<0||nd.a[i].x==n||nd.a[i].y==m) nd.a[i].x=n,nd.a[i].y=m;
		else
		{
			while(tmp[nd.a[i].x][nd.a[i].y]) nd.a[i].x-=dx[nd.dir],nd.a[i].y-=dy[nd.dir];
			tmp[nd.a[i].x][nd.a[i].y]=1;
		}
	}
	return nd;
}
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	node st,eee;
	int ans=-1;
	st.dir=0;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		char op;
		cin>>op;
		if(op=='w') mp[i][j]=1;
		else mp[i][j]=0;
		if(op=='b') eee.a[k]={n,m},st.a[k++]={i,j};
	}
	for(int i=0;i<4;i++) eee.dir=i,en[eee.get()]=1;
	for(int i=0;i<m;i++) nxt[0][n-1][i]=mp[n-1][i]?n-1:-114;
	for(int i=n-2;i>=0;i--) for(int j=0;j<m;j++) nxt[0][i][j]=mp[i][j]?i:nxt[0][i+1][j];
	for(int i=0;i<n;i++) nxt[1][i][m-1]=mp[i][m-1]?m-1:-114;
	for(int j=m-2;j>=0;j--) for(int i=0;i<n;i++) nxt[1][i][j]=mp[i][j]?j:nxt[1][i][j+1];
	for(int i=0;i<m;i++) nxt[2][0][i]=mp[0][i]?0:-114;
	for(int i=1;i<n;i++) for(int j=0;j<m;j++) nxt[2][i][j]=mp[i][j]?i:nxt[2][i-1][j];
	for(int i=0;i<n;i++) nxt[3][i][0]=mp[i][0]?0:-114;
	for(int j=1;j<m;j++) for(int i=0;i<n;i++) nxt[3][i][j]=mp[i][j]?j:nxt[3][i][j-1];
	queue<pair<node,int>> q;
	q.push({st,0}),st.tagall();
	while(q.size())
	{
		node p=q.front().first;int dis=q.front().second;q.pop();
		if(en[p.get()])
		{
			ans=dis;
			break;
		}
		{
			node pp=turn(p,1);
			if(!to[pp.get()]) pp.tagall(),q.push({pp,dis+1});
		}
		{
			node pp=turn(p,-1);
			if(!to[pp.get()]) pp.tagall(),q.push({pp,dis+1});
		}
	}
	cout<<ans<<"\n";
	return 0;
}