引爆炸弹 - 来自计蒜客小学期

题目：

题意分析：

1.引爆一个炸弹，则属于该行该列的炸弹都会被引爆，结果被引爆的每个炸弹也递归引爆剩余的炸弹

2.最少需要手动引爆多少个，我们可以把会连续引爆的炸弹们归为同一个集合里面，这个集合里的任何一个炸弹被引爆，整个集合都会被引爆。因此这个集合的所有炸弹是等效的

3.那么我们只需要首先引爆某个炸弹，然后对集合进行标记引爆，搜索染色直到所有炸弹都炸了。

思路：

1. 统计地图中的所有炸弹和炸弹坐标

2. 先引爆某个炸弹

3. 对这个炸弹所在的集合进行染色

4. 深搜，即枚举剩下的炸弹，找到剩下的集合 如果找到了 则手动的步数+1

注意：

1. 只需要进行染色即可 不需要recolor

2. dfs起点只需要随意一个炸弹即可

3. 地图没有存储的必要

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 666
char map[MAXN][MAXN];
int n, m;
int ans = MAXN * MAXN;
struct BOMB
{
    int x, y;
} bombs[MAXN * MAXN];
struct VISB
{
    char visb;
    int father;
} visb[MAXN * MAXN];
int bombcnt;
int exploded;
int queue[MAXN*MAXN],tot;
inline int same_block(int i, int j)
{
    if ((bombs[i].x == bombs[j].x) || (bombs[i].y == bombs[j].y))
    {
        return 1;
    }
    return 0;
}
void color_dfs(int b)
{
    queue[++tot] = b;
    while(tot!=0)
    {
        int x = queue[tot--];
        for(int i = 0;i<bombcnt;i++)
        {
            if(same_block(x,i)&&!visb[i].visb)
            {
                exploded++;
                if(exploded==bombcnt)
                {
                    return;
                }
                visb[i].visb = 1;
                visb[i].father = x;
                queue[++tot] = i;
            }
        }
    }
}
void decolor_dfs(int b)
{
    queue[++tot] = b;
    while(tot!=0)
    {
        int x = queue[tot--];
        for(int i =0;i<bombcnt;i++)
        {
            if(same_block(x,i)&&visb[i].visb&&visb[i].father==x)
            {
                visb[i].visb = 0;
                exploded--;
                visb[i].father = -1;
                queue[++tot] = i;
            }
        }
    }
}

int dfs(int b, int cnt)
{
    if (cnt > ans)
    {
        return 0;
    }
    color_dfs(b);
    if (exploded == bombcnt)
    {
        printf("%d",cnt);
        return 1;
    }
    for (int i = 0; i < bombcnt; i++)
    {
        if (!visb[i].visb)
        {
            if(dfs(i, cnt + 1))
            {
                return 1;
            }
        }
    }
    //decolor_dfs(b);
    return 0;
}
int main()
{
    freopen("E:\\Downloads\\4.txt","r",stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", map[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == '1')
            {
                bombs[bombcnt].x = i;
                bombs[bombcnt].y = j;
                bombcnt++;
            }
        }
    }

    dfs(rand()%bombcnt, 1);

}