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

SunburstFan · 2025-05-10 14:36:01 · 题解

P11906 [NHSPC 2023] E. 迷宫钥匙圈

题目大意

给定一个由字母表示的迷宫面板,每一次将迷宫向左或向右旋转 90 度，所有还在迷宫内的小钢珠会按照特定规则“下落”——直到掉出迷宫、碰到挡板或碰到其它已停稳的小钢珠。求至少需要多少次旋转（仅允许左旋或右旋）才能使所有小钢珠都掉出迷宫。

解题思路

搜索题。

将迷宫看作二维矩阵，每次旋转分别实现左旋或右旋操作。

对于旋转后的矩阵，逐列模拟小钢珠的下落过程：

• 找到每个小钢珠下降路径中最先遇到的挡板，并根据该列已有的小钢珠数确定最终落点；
• 若该列没有挡板，则对应的小钢珠会掉出迷宫（状态中移除）。

将每一次旋转后的状态（迷宫中小钢珠的位置配置）作为一个状态节点，用 BFS 从初始状态开始搜索：

• 当某状态下迷宫中已无小钢珠时，即找到答案，输出所需旋转次数；
• 若遍历所有可能状态都无法清空小钢珠，则输出 -1。

#include<iostream>
#include<cstring>
#include<queue>
#include<array>

using namespace std;

const int N=17;

int f[N][N][N][N][N][N][2];
char s[N+1][N+1];
int n,m;

namespace sunburstfan{
    int check(int x,int y){
        if(x+y==0)return 1;
        if(x<1||x>n)return 1;
        if(y<1||y>m)return 1;
        return 0;
    }

    bool left_rotate(int x[3],int y[3],int res,queue<array<int,7>>&q){
        int xx[3]={0},yy[3]={0},d[3]={0};

        for(int i=0;i<=2;i++){
            if(check(x[i],y[i])){
                xx[i]=x[i];
                yy[i]=y[i];
                continue;
            }
            xx[i]=x[i];
            for(int j=y[i]-1;j>=0;j--){
                if(!j||s[x[i]][j]=='w'){
                    yy[i]=j+(j>0);
                    break;
                }
            }
        }

        if(check(xx[0],yy[0])&&check(xx[1],yy[1])&&check(xx[2],yy[2])){
            return true;
        }

        for(int i=0;i<=2;i++){
            d[i]=0;
            for(int j=0;j<=2;j++){
                if(j==i)continue;
                if(x[j]==x[i]&&y[j]<y[i]&&y[j]>=yy[i])d[i]++;
            }
        }

        for(int i=0;i<=2;i++)yy[i]+=d[i];

        if(f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][1]>res+1){
            f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][1]=res+1;
            q.push({xx[0],yy[0],xx[1],yy[1],xx[2],yy[2],1});
        }

        return false;
    }

    bool right_rotate(int x[3],int y[3],int res,queue<array<int,7>>&q){
        int xx[3]={0},yy[3]={0},d[3]={0};

        for(int i=0;i<=2;i++){
            if(check(x[i],y[i])){
                xx[i]=x[i];
                yy[i]=y[i];
                continue;
            }
            xx[i]=x[i];
            for(int j=y[i]+1;j<=m+1;j++){
                if(j>m||s[x[i]][j]=='w'){
                    yy[i]=j-(j<=m);
                    break;
                }
            }
        }

        if(check(xx[0],yy[0])&&check(xx[1],yy[1])&&check(xx[2],yy[2])){
            return true;
        }

        for(int i=0;i<=2;i++){
            d[i]=0;
            for(int j=0;j<=2;j++){
                if(j==i)continue;
                if(x[j]==x[i]&&y[j]>y[i]&&y[j]<=yy[i])d[i]++;
            }
        }

        for(int i=0;i<=2;i++)yy[i]-=d[i];

        if(f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][1]>res+1){
            f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][1]=res+1;
            q.push({xx[0],yy[0],xx[1],yy[1],xx[2],yy[2],1});
        }

        return false;
    }

    bool up_rotate(int x[3],int y[3],int res,queue<array<int,7>>&q){
        int xx[3]={0},yy[3]={0},d[3]={0};

        for(int i=0;i<=2;i++){
            if(check(x[i],y[i])){
                xx[i]=x[i];
                yy[i]=y[i];
                continue;
            }
            yy[i]=y[i];
            for(int j=x[i]-1;j>=0;j--){
                if(!j||s[j][y[i]]=='w'){
                    xx[i]=j+(j>0);
                    break;
                }
            }
        }

        if(check(xx[0],yy[0])&&check(xx[1],yy[1])&&check(xx[2],yy[2])){
            return true;
        }

        for(int i=0;i<=2;i++){
            d[i]=0;
            for(int j=0;j<=2;j++){
                if(j==i)continue;
                if(y[j]==y[i]&&x[j]<x[i]&&x[j]>=xx[i])d[i]++;
            }
        }

        for(int i=0;i<=2;i++)xx[i]+=d[i];

        if(f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][0]>res+1){
            f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][0]=res+1;
            q.push({xx[0],yy[0],xx[1],yy[1],xx[2],yy[2],0});
        }

        return false;
    }

    bool down_rotate(int x[3],int y[3],int res,queue<array<int,7>>&q){
        int xx[3]={0},yy[3]={0},d[3]={0};

        for(int i=0;i<=2;i++){
            if(check(x[i],y[i])){
                xx[i]=x[i];
                yy[i]=y[i];
                continue;
            }
            yy[i]=y[i];
            for(int j=x[i]+1;j<=n+1;j++){
                if(j>n||s[j][y[i]]=='w'){
                    xx[i]=j-(j<=n);
                    break;
                }
            }
        }

        if(check(xx[0],yy[0])&&check(xx[1],yy[1])&&check(xx[2],yy[2])){
            return true;
        }

        for(int i=0;i<=2;i++){
            d[i]=0;
            for(int j=0;j<=2;j++){
                if(j==i)continue;
                if(y[j]==y[i]&&x[j]>x[i]&&x[j]<=xx[i])d[i]++;
            }
        }

        for(int i=0;i<=2;i++)xx[i]-=d[i];

        if(f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][0]>res+1){
            f[xx[0]][yy[0]][xx[1]][yy[1]][xx[2]][yy[2]][0]=res+1;
            q.push({xx[0],yy[0],xx[1],yy[1],xx[2],yy[2],0});
        }

        return false;
    }
}
using namespace sunburstfan;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(f,0x3f,sizeof(f));

    cin>>n>>m;
    int sx1=0,sy1=0,sx2=0,sy2=0,sx3=0,sy3=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
            if(s[i][j]=='b'){
                if(!sx1)sx1=i,sy1=j;
                else if(!sx2)sx2=i,sy2=j;
                else if(!sx3)sx3=i,sy3=j;
            }
        }
    }

    queue<array<int,7>>q;
    int id=0;
    f[sx1][sy1][sx2][sy2][sx3][sy3][0]=0;
    q.push({sx1,sy1,sx2,sy2,sx3,sy3,id});

    while(!q.empty()){
        int x[3],y[3];
        x[0]=q.front()[0],y[0]=q.front()[1];
        x[1]=q.front()[2],y[1]=q.front()[3];
        x[2]=q.front()[4],y[2]=q.front()[5];
        id=q.front()[6];
        q.pop();

        int res=f[x[0]][y[0]][x[1]][y[1]][x[2]][y[2]][id];

        if(!id){
            if(left_rotate(x,y,res,q)){
                cout<<res+1;
                return 0;
            }

            if(right_rotate(x,y,res,q)){
                cout<<res+1;
                return 0;
            }
        }
        else{
            if(up_rotate(x,y,res,q)){
                cout<<res+1;
                return 0;
            }

            if(down_rotate(x,y,res,q)){
                cout<<res+1;
                return 0;
            }
        }
    }

    cout<<-1;
    return 0;
}