bubble shooter(dfs).cpp

杭电acm解题报告2001---2099.

//先dfs搜打掉的球数
//再dfs2搜会掉下来的球数
//注意状态保存和球粘连关系就好了
#include <cstdio>
#include <string>
using namespace std;
int H,W,h,w;
char map[110][110];
bool v[110][110];
char color;
int shoot;
int d[2][6][2] =
{
    {{0,-1},{0,1},{-1,0},{-1,1},{1,0},{1,1}},
    {{0,-1},{0,1},{-1,0},{-1,-1},{1,0},{1,-1}}
};

void dfs(int x,int y)
{ 
    if(x<=0 || x>H)
        return ;
    if(y<=0 || y>W-(x+1)%2)
        return ;
    if(map[x][y-1] == color)
    {
        shoot ++;
        map[x][y-1] = 'E';
        for (int i=0;i<6;i++) {
            dfs( x+d[x%2][i][0], y+d[x%2][i][1] );
        }
    }
}

bool dfs2(int x,int y)
{
    char ch;

    if(x<=0) return true;
    if(y<=0 || y>W-(x+1)%2 || x>H)
        return false;
    if(map[x][y-1] == 'E')
        return false;
    else
    {
        shoot ++;
        ch = map[x][y-1];
        map[x][y-1] = 'E';
        v[x][y-1] = true;
        for (int i=0;i<6;i++) {
            if ( dfs2( x+d[x%2][i][0], y+d[x%2][i][1] ) ) {
                map[x][y-1] = ch;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int i,j,ans,total;
    
    while( scanf("%d %d %d %d",&H,&W,&h,&w)!=EOF )
    {
        for(i=1;i<=H;i++)
            scanf("%s",map[i]);
        memset(v,0,sizeof(v));
        
        color = map[h][w-1];
        ans = 0;
        shoot = 0;
        if (color != 'E') {
            dfs(h,w);
            if(shoot >= 3)    ans += shoot;
            else {
                printf("0\n");
                continue;
            }
            for (i=1; i<=H ;i++) {
                for (j=1; j<=W-(i+1)%2 ;j++) {
                    shoot = 0;
                    if( !v[i][j-1] && map[i][j-1]!='E' && !dfs2(i,j) ) {
                        ans += shoot;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}