Problem Description
Bomberman has been a very popular game ever since it was released. As you can see above, the game is played in an N*M rectangular room. Bomberman can go around the room and place bombs. Bombs explode in 4 directions with radius r.
To finish a stage, bomberman has to defeat all the foes with his bombs and find an exit behind one of the walls.
Since time is limited, bomberman has to do this job quite efficiently. Now he has successfully defeated all the foes, and is searching for the exit. It's really troublesome to destroy the walls one by one, so he's asking for your help to calculate the minimal
number of bombs he has to place in order to destroy all the walls, thus he can surely find the exit.
To finish a stage, bomberman has to defeat all the foes with his bombs and find an exit behind one of the walls.
Since time is limited, bomberman has to do this job quite efficiently. Now he has successfully defeated all the foes, and is searching for the exit. It's really troublesome to destroy the walls one by one, so he's asking for your help to calculate the minimal
number of bombs he has to place in order to destroy all the walls, thus he can surely find the exit.
Input
The input contains several cases. Each case begins with two integers: N and M(4 <= N, M <= 15). N lines follow, each contains M characters, describing the room. A '*' means a concrete wall which can never be destroyed, a '#' is an
ordinary wall that can be destroyed by a single bomb, a '.' is an empty space where bombs can only be placed. There're at most 30 ordinary walls. The borders of the room is always surrounded by concrete walls, as you can see from the samples. You may assume
that the explosion radius r is infinite, so that an explosion can reach as far as possible until it meets a wall and destroys it if it's an ordinary one. Proceed until the end of file.
ordinary wall that can be destroyed by a single bomb, a '.' is an empty space where bombs can only be placed. There're at most 30 ordinary walls. The borders of the room is always surrounded by concrete walls, as you can see from the samples. You may assume
that the explosion radius r is infinite, so that an explosion can reach as far as possible until it meets a wall and destroys it if it's an ordinary one. Proceed until the end of file.
Output
For each case, output the minimal number of bombs that should be placed to destroy all the ordinary walls. Note that two bombs can't be placed at the same position and all bombs explode simultaneously, which makes the result for the
second sample to be 3 instead of 2. You may assume that there's always a solution.
second sample to be 3 instead of 2. You may assume that there's always a solution.
Sample Input
9 11 *********** *#.#...#.#* *.*.*.*.*.* *.........* *.*.*.*.*.* *....#....* *.*.*.*.*.* *....#....* *********** 3 13 ************* *..##...##..* *************
Sample Output
3 3
Source
解题思路：
最近竟然和炸弹人分不开了，从啊哈算法开始讲解无穷枚举到BFS和DFS，都是通过炸弹人来实现的，现在学了DLX的时候，也是通过炸弹人来入门，
其实，很简单的一个炸弹人，裸裸的DLX，对于DLX的学习，在这里不多说了， 我会开一个有关DLX的详细贴，到时候大家和我可以一同认真学习啊。
# include<cstdio>
# include<iostream>
# include<cstring>
# include<algorithm>
# define MAXM 20
# define MAXN 60000
# define MAXL 300
# define INF 0x7FFFFFFF
using namespace std;
char s[MAXM][MAXM];
int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
int H[MAXL], S[MAXL], C[MAXN];
int pos[MAXM][MAXM], ans, size;
bool vis[MAXL];
void Init(int n)
{
int i;
for (i = 0; i <= n; i++)
{
R[i] = i + 1;
L[i + 1] = i;
U[i] = D[i] = i;
S[i] = 0;
}
R[n] = 0;
size = n + 1;
}
void Link(int r, int c)
{
U[size] = c;
D[size] = D[c];
U[D[c]] = size;
D[c] = size;
if (H[r] < 0)
H[r] = L[size] = R[size] = size;
else
{
L[size] = H[r];
R[size] = R[H[r]];
L[R[H[r]]] = size;
R[H[r]] = size;
}
S[c]++;
C[size++] = c;
}
void Remove(int c)
{
int i;
for (i = D[c]; i != c; i = D[i])
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void Resume(int c)
{
int i;
for (i = D[c]; i != c; i = D[i])
L[R[i]] = R[L[i]] = i;
}
int A()
{
int i, j, k, res;
memset(vis, false, sizeof(vis));
for (res = 0, i = R[0]; i; i = R[i])
{
if (!vis[i])
{
res++;
for (j = D[i]; j != i; j = D[j])
{
for (k = R[j]; k != j; k = R[k])
vis[C[k]] = true;
}
}
}
return res;
}
void Dance(int now)
{
if (R[0] == 0)
ans = min(ans, now);
else if (now + A() < ans)
{
int i, j, temp, c;
for (temp = INF,i = R[0]; i; i = R[i])
{
if (temp > S[i])
{
temp = S[i];
c = i;
}
}
for (i = D[c]; i != c; i = D[i])
{
Remove(i);
for (j = R[i]; j != i; j = R[j])
Remove(j);
Dance(now + 1);
for (j = L[i]; j != i; j = L[j])
Resume(j);
Resume(i);
}
}
}
int main(void)
{
int n, m, i, j, k, r;
while (~scanf("%d%d", &n, &m))
{
memset(pos, 0, sizeof(pos));
for (i = k = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
scanf(" %c", &s[i][j]);
if (s[i][j] == '#')
{
k++;
pos[i][j] = k;
}
}
}
Init(k);
for (i = r = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
H[++r] = -1;
if (s[i][j] == '.')
{
for (k = j + 1; k < m && s[i][k] == '.'; k++)
;
if (s[i][k] == '#')
Link(r, pos[i][k]);
for (k = j - 1; k >= 0 && s[i][k] == '.'; k--)
;
if (s[i][k] == '#')
Link(r, pos[i][k]);
for (k = i + 1; k < n && s[k][j] == '.'; k++)
;
if (s[k][j] == '#')
Link(r, pos[k][j]);
for (k = i - 1; k >= 0 && s[k][j] == '.'; k--)
;
if (s[k][j] == '#')
Link(r, pos[k][j]);
}
}
}
ans = INF;
Dance(0);
printf("%d\n", ans);
}
return 0;
}