题解：P11906 [THSPC 2023] E. 迷宫钥匙圈

· · 题解

题目传送门

诈骗题。

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

题目分析

以下记小钢珠的数量为 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;
}