题解 P5121 【[USACO18DEC]Mooyo Mooyo】

Hexarhy · 2019-05-12 13:38:54 · 题解

思路：搜索

一看到题目，立马就想到了搜索进行染色。几个要点：

• 第一步是消。那我们就找联通块，判断遍历个数是否有k个，然后再搜一遍进行染色。

• 第二步下落。像消消乐一样，我们可以把大问题分解成简单问题。对于一个宽度只有1的棋盘，我们只需要从下往上搜，遇到0，就把它上面依次往下挪同一个距离。稍微画图就很容易想到。那么对于宽度为10的棋盘，也只是多加一层循环而已。

• 最后还要判断是否消完，是不是要重复上述步骤。是否消完其实就看是否有k大小的联通块。不妨用一个\mathrm{bool}，每次搜索前都是\mathrm{false}。在找联通块的时候，一遇到超过k的，就直接赋值为\mathrm{true}。如果搜完了还是\mathrm{false}，说明已经消完了。

• 另外，由于\mathrm{bool}的初始值是\mathrm{false}，可\mathrm{while}里是要求\mathrm{true}，故采用do-while。

• 对于读入，由于数字之间没有空格，不能用普通的cin和scanf("%d")，但是scanf("%1d")可以强制每次只读入一个数位。

• CCF提醒您，搜索千万遍，清空第一条。求解不清空，WA两行泪。

另外，数组的横纵坐标要注意，请自行想清楚了来把握。

由于数据太小，所以上述搜索是不会超时的，尽管感觉用了很多循环。

其它的程序会体现。

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

const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};//搜索的四个方向
const int MAXN=250;
int n,k,s;
int a[MAXN][MAXN];
bool visit[MAXN][MAXN];
bool f;//判断是否消完

void input(void)
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=10;j++)
      scanf("%1d",&a[i][j]);//每次只读入一个数位
}

void count(const int x,const int y,const int col)//统计联通块的个数
{
    if(x<1 || x>n || y<1 || y>10 || visit[x][y] || a[x][y]!=col)
     return;
    visit[x][y]=true;
    s++;//统计
    for(int i=0;i<4;i++)
        count(dx[i]+x,dy[i]+y,col);
}

void disappear(const int x,const int y,const int col)//消除，变为0
{
    if(x<1 || x>n || y<1 || y>10 || visit[x][y] || a[x][y]!=col)
     return;
    visit[x][y]=true;
    a[x][y]=0;//消除
    for(int i=0;i<4;i++)
        count(dx[i]+x,dy[i]+y,col);
}

void drop(void)//下落
{
    for(int i=1;i<=10;i++)//棋盘每一列逐个下落
     for(int j=n;j>=1;j--)//从下往上搜
      if(a[j][i]==0)//遇到了一个0
       for(int k=j;k>=1;k--)//从当前0的位置出发，继续往上搜，并依次赋值
        if(a[k][i])
        {
            a[j][i]=a[k][i];
            a[k][i]=0;//掉落之后该位置就是空的了
            break;//这个break是干什么的窝忘了QAQ
        }
}

void solve(void)
{
    do//上文讲过为什么采用do-while
    {
        f=false;//每次搜索前都要赋值
        for(int i=1;i<=n;i++)
         for(int j=1;j<=10;j++)
        {
            if(a[i][j]==0)//空格没必要搜
             continue;
            s=0;//联通块个数在搜索之前记得清零
            memset(visit,false,sizeof(visit));//别忘了清空
            count(i,j,a[i][j]);
            if(s>=k)
            {
                f=true;//只要有一个符合要求，f就为true
                memset(visit,false,sizeof(visit));//别忘了清空
                disappear(i,j,a[i][j]);
            }   
        }
        memset(visit,false,sizeof(visit));//别忘了清空
        drop();//注意掉落是所有染色完了之后再掉落的
    }while(f);
}

void output(void)
{
    for(int i=1;i<=n;i++,puts(""))
     for(int j=1;j<=10;j++)
      printf("%d",a[i][j]);
}

int main()
{
//  freopen("mooyomooyo.in","r",stdin);
//  freopen("mooyomooyo.out","w",stdout);
    input();
    solve();
    output();
    return 0;
}