1. 首页
2. DFS
3. 本页

ZOJ 2743 Bubble Shooter （搜索）

新增加的泡泡如果跟周围同色的泡泡相连个数>=3，他们就会爆炸，还有不是头顶第一排相连的，也会爆炸，先处理下跟新增加的泡泡相连的泡泡，然后再统计头顶相连的泡泡。。奇偶行泡泡个数不一样，所以要分开处理。。

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int MAXN = 10000;

int n,m;
int sx,sy;
int dirx[2][8]= {{-1,-1,1,1, 0,0},{-1,-1, 1,1, 0,0}};
int diry[2][8]= {{ 0, 1,0,1,-1,1},{-1, 0,-1,0,-1,1}};
int a[150][150];
int cnt;

void fd(int x,int y,int res)
{
    a[x][y]=-1;
    cnt++;
    for(int i=0; i<6; ++i)
    {
        int xx=x+dirx[x%2][i];
        int yy=y+diry[x%2][i];

        if(a[xx][yy]==res)
        {
            fd(xx,yy,res);
        }
    }

}

void fd2(int x,int y)
{
    a[x][y]=-1;
    cnt++;
    for(int i=0; i<6; ++i)
    {
        int xx=x+dirx[x%2][i];
        int yy=y+diry[x%2][i];
        if(a[xx][yy]>0)
        {
            fd2(xx,yy);
        }
    }
}

char tmp[150];

int main()
{
    while(cin>>n>>m>>sx>>sy)
    {
        memset(a,0,sizeof(a));
        int ans=0;
        for(int i=1; i<=n; ++i)
        {
            scanf("%s",tmp);
            for(int j=0; j<strlen(tmp); ++j)
            {
                if(tmp[j]>='a' && tmp[j]<='z')
                {
                    a[i][j+1]=tmp[j]-'a'+1;
                    ans++;
                }
            }
        }

        cnt=0;
        fd(sx,sy,a[sx][sy]);
        //cout<<cnt<<endl;
//        for(int i=1; i<=n; ++i)
//        {
//            for(int j=1; j<=n; ++j)
//            {
//                cout<<a[i][j]<<" ";
//            }
//            puts("");
//        }
        if(cnt<3)
        {
            for(int i=1; i<=n; ++i)
            {
                for(int j=1; j<=m; ++j)
                {
                    if(a[i][j]==-1)
                    {
                        a[i][j]='E';
                    }
                }
            }
        }
        cnt=0;
        for(int i=1; i<=m; ++i)
        {
            if(a[1][i]>0)
            {
                fd2(1,i);
            }
        }

        cout<<ans-cnt<<endl;


    }

    return 0;
}