[BZOJ1501/Luogu4205][NOI2005]智慧珠游戏(搜索)

发布于 2018-02-27  112 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1501/Luogu4205][NOI2005]智慧珠游戏(搜索)

Description

BZOJ1501-1

Http

BZOJ
Luogu

Tag

搜索

解决思路

把每一种状态的旋转和翻折全部找出来,大力搜索即可。注意开局可以判断一下合法情况,若出现连通数小于等于\(2\)的联通块,则直接无解。
(哈哈,代码没有超过200行)

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define RG register
#define IL inline

class Pos
{
public:
    int x,y;
};

Pos operator + (Pos A,Pos B)
{
    return (Pos){A.x+B.x,A.y+B.y};
}

class Vector
{
public:
    int num;
    Pos P[5];
};

const int maxN=14;
const int mPos=10;
//下面Vec记录每一个合法摆放联通块的信息,每一行表示同一组,即通过旋转和翻折可以变成一样的零件
const Vector Vec[60]={(Vector){3,(Pos){0,0},(Pos){1,0},(Pos){0,1}},(Vector){3,(Pos){0,0},(Pos){0,1},(Pos){1,1}},(Vector){3,(Pos){0,0},(Pos){1,0},(Pos){1,1}},(Vector){3,(Pos){0,0},(Pos){1,0},(Pos){1,-1}},
                    (Vector){4,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){0,3}},(Vector){4,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){3,0}},
                    (Vector){4,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){1,0}},(Vector){4,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){2,1}},(Vector){4,(Pos){0,0},(Pos){1,0},(Pos){1,-1},(Pos){1,-2}},(Vector){4,(Pos){0,0},(Pos){0,1},(Pos){1,1},(Pos){2,1}},(Vector){4,(Pos){0,0},(Pos){1,0},(Pos){1,1},(Pos){1,2}},(Vector){4,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){0,1}},(Vector){4,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){1,2}},(Vector){4,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){2,-1}},
                    (Vector){4,(Pos){0,0},(Pos){1,0},(Pos){0,1},(Pos){1,1}},
                    (Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){2,1},(Pos){2,2}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){1,2},(Pos){2,2}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){1,0},(Pos){2,0}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){2,-1},(Pos){2,-2}},
                      (Vector){5,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){0,3},(Pos){1,1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){0,3},(Pos){1,2}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,-1},(Pos){1,1},(Pos){1,2}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,-2},(Pos){1,-1},(Pos){1,1}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){3,0},(Pos){2,1}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){2,-1},(Pos){3,0}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,1},(Pos){2,0},(Pos){3,0}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,-1},(Pos){2,0},(Pos){3,0}},
                    (Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){0,2},(Pos){1,2}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,1},(Pos){1,2},(Pos){0,2}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){2,0},(Pos){2,1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,1},(Pos){2,1},(Pos){2,0}},
                      (Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){1,1},(Pos){0,2}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,1},(Pos){0,2},(Pos){1,2}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,1},(Pos){2,0},(Pos){2,1}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){1,-1},(Pos){2,-1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){1,1},(Pos){1,2}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){1,1},(Pos){1,-1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){1,1},(Pos){2,1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){1,1},(Pos){2,0}},
                    (Vector){5,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){1,2},(Pos){1,3}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){2,-1},(Pos){3,-1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,1},(Pos){1,2},(Pos){1,3}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,-1},(Pos){2,-1},(Pos){3,-1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){1,-1},(Pos){1,-2}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,1},(Pos){2,1},(Pos){3,1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){1,0},(Pos){1,-1}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){2,1},(Pos){3,1}},
                    (Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,-1},(Pos){1,1},(Pos){2,0}},
                      (Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,1},(Pos){2,1},(Pos){2,2}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,-1},(Pos){2,-1},(Pos){2,-2}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){1,-1},(Pos){2,-1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,1},(Pos){1,2},(Pos){2,2}},
                    (Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,-1},(Pos){1,-2},(Pos){1,-3}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){1,1},(Pos){1,2},(Pos){1,3}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){3,0},(Pos){3,-1}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){2,0},(Pos){3,0},(Pos){3,1}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){0,2},(Pos){0,3},(Pos){1,3}},(Vector){5,(Pos){0,0},(Pos){1,0},(Pos){0,1},(Pos){0,2},(Pos){0,3}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,0},(Pos){2,0},(Pos){3,0}},(Vector){5,(Pos){0,0},(Pos){0,1},(Pos){1,1},(Pos){2,1},(Pos){3,1}}};
const int F1[5]={0,1,-1,0,0};
const int F2[5]={0,0,0,-1,1};
const int inf=2147483647;

char Map[maxN][maxN];
char Opt[62]={"AAAABBCCCCCCCCDEEEEFFFFFFFFGGGGHHHHHHHHIIIIIIIIJKKKKLLLLLLLL"};
bool vis[100];
bool get_ans=0;
Pos Queue[maxN*maxN];

void dfs(int x,int y);
IL bool Check(RG int x,RG int y,RG int f);
IL void Cover(RG int x,RG int y,RG int f,RG char ch);
IL bool Bfs();

int main()
{
    ios::sync_with_stdio(false);
    for (RG int i=1;i<=10;i++)
        for (RG int j=1;j<=i;j++)
        {
            RG char opt;cin>>opt;
            Map[i][j]=opt;
            if (Map[i][j]!='.') vis[Map[i][j]]=1;
        }
    if (Bfs()==1) dfs(1,1);
    if (get_ans==0) printf("No solution\n");
    return 0;
}

void dfs(RG int x,RG int y)//搜索
{
    if (y>x) x++,y=1;
    if (x==11)
    {
        for (RG int i=1;i<=10;i++)
        {
            for (RG int j=1;j<=i;j++) printf("%c",Map[i][j]);
            printf("\n");
        }
        fclose(stdin);fclose(stdout);
        get_ans=1;
        return;
    }
    if (Map[x][y]!='.') dfs(x,y+1);
    for (RG int i=0;(i<=59)&&(get_ans==0);i++)//59种方式
        if (vis[Opt[i]]==0)
            if (Check(x,y,i))//检查这样摆放是否合法
            {
                vis[Opt[i]]=1;
                Cover(x,y,i,Opt[i]);//摆放
                dfs(x,y+1);
                Cover(x,y,i,'.');//修复回来
                vis[Opt[i]]=0;
            }
    return;
}

IL bool Check(RG int x,RG int y,RG int f)
{
    RG int x2,y2;
    for (RG int i=0;i<Vec[f].num;i++)
    {
        x2=x+Vec[f].P[i].x;y2=y+Vec[f].P[i].y;
        if (Map[x2][y2]!='.') return 0;
    }
    return 1;
}

IL void Cover(RG int x,RG int y,RG int f,RG char ch)
{
    for (RG int i=0;i<Vec[f].num;i++)
        Map[x+Vec[f].P[i].x][y+Vec[f].P[i].y]=ch;
    return;
}

int histcnt=0;
int inqueue[maxN][maxN];

IL bool Bfs()
{
    histcnt++;
    for (RG int i=1;i<=10;i++)
        for (RG int j=1;j<=i;j++)
            if ((inqueue[i][j]!=histcnt)&&(Map[i][j]=='.'))
            {
                RG int h=1,t=0;
                Queue[1]=(Pos){i,j};inqueue[i][j]=histcnt;
                do
                {
                    RG Pos u=Queue[++t];
                    for (int f=1;f<=4;f++)
                        if ((u.x+F1[f]>=1)&&(u.x+F1[f]<=10)&&(u.y+F2[f]>=1)&&(u.y+F2[f]<=10)&&(Map[u.x+F1[f]][u.y+F2[f]]=='.')&&(inqueue[u.x+F1[f]][u.y+F2[f]]!=histcnt))
                        {
                            Queue[++h]=(Pos){u.x+F1[f],u.y+F2[f]};
                            inqueue[u.x+F1[f]][u.y+F2[f]]=histcnt;
                        }
                }
                while (t!=h);
                if (h<=2) return 0;
            }
    return 1;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1501/Luogu4205][NOI2005]智慧珠游戏(搜索)


HNCJ OIer