hdu2258 Continuous Same Game (一)

hdu2258 Continuous Same Game (1)

此题是模拟消除游戏，根据题目的策略，优先消除数量最多且X、Y坐标更小的连通块，n，m范围在20以内，模拟即可。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=25;
int n,m;
int mp[maxn][maxn],vis[maxn][maxn];
struct ty
{
    int x,y;
};
queue<ty> q;
int ok(int x,int y) {return x>=0&&x<n&&y>=0&&y<m;}
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int bfs(int x,int y,int key)
{
    int ans=1;
    while (!q.empty()) q.pop();
    ty st;
    st.x=x;
    st.y=y;
    q.push(st);
    vis[x][y]=1;
    while (!q.empty())
    {
        ty &now=q.front();
        for (int i=0;i<4;i++)
        {
            int nx=now.x+dx[i];
            int ny=now.y+dy[i];
            ty exp;
            exp.x=nx;
            exp.y=ny;
            if (ok(nx,ny)&&!vis[nx][ny]&&mp[nx][ny]==key)
            {
                vis[nx][ny]=1;
                ans++;
                q.push(exp);
            }
        }
        q.pop();
    }
    return ans;
}
int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(mp,0,sizeof(mp));
        for (int i=0;i<n;i++)
            for (int j=0;j<m;j++)
                scanf("%1d",&mp[i][j]);
        int ans=0;
        while (1)		//循环至不能消除为止
        {
            int x,y,k=0;
            memset(vis,0,sizeof(vis));
            for (int i=0;i<n;i++)			//枚举每个位置点
                for (int j=0;j<m;j++)
                    if (mp[i][j]!=0)
                    {
                        int tmp=bfs(i,j,mp[i][j]);		//算出这个位置能消除的个数
                        if (tmp>k)
                        {
                            k=tmp;
                            x=i;
                            y=j;
                        }
                    }
            if (k<=1) break;			//不能消除，退出循环
            ans+=k*(k-1);				
            memset(vis,0,sizeof(vis));
            bfs(x,y,mp[x][y]);
            for (int i=0;i<n;i++)			//将消除的位置赋值为0
                for (int j=0;j<m;j++)
                    if (vis[i][j])
                        mp[i][j]=0;
            for (int time=0;time<=n;time++)		//消除列下面的0
            for (int j=0;j<m;j++)
            {
                for (int i=n-1;i>=0;i--)
                    if (mp[i][j]==0)
                    {
                        for (int l=i;l>=1;l--)
                            mp[l][j]=mp[l-1][j];
                        mp[0][j]=0;
                    }
            }
            for (int time=0;time<=m;time++)	//消除空行
            for (int j=0;j<m;j++)
                if (mp[n-1][j]==0)
                {
                    for (int l=j;l<m-1;l++)
                        for (int i=0;i<n;i++)
                            mp[i][l]=mp[i][l+1];
                    for (int i=0;i<n;i++)
                        mp[i][m-1]=0;
                }
        }
        printf("%d\n",ans);
    }
    return 0;
}