JZOJ 3252. 【GDOI三校联考】炸弹

思路

注：上图只是个例子，其实建图时 (5) 是不会连向 (6) 的

(Code)

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int n , m , mp[55][55] , f[55 * 55][4] , tot , vis[55 * 55] , h[55 * 55] , rt;

struct edge{
	int to , nxt;
}e[55 * 55 * 2];

inline int getid(int x , int y){return (x - 1) * m + y;}
inline void add(int x , int y)
{
	e[++tot] = (edge){y , h[x]};
	h[x] = tot;
	e[++tot] = (edge){x , h[y]};
	h[y] = tot;
}

inline void dfs(int x)
{
	vis[x] = 1;
	int mi = 1e7 , sum = 0;
	for(register int i = h[x]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if (vis[v]) continue;
		dfs(v);
		f[x][0] += f[v][1] , sum += min(min(f[v][0] , f[v][1]) , f[v][2]);
		mi = min(mi , f[v][2] - min(min(f[v][0] , f[v][1]) , f[v][2]));
	}
	f[x][1] = sum + mi , f[x][2] = sum + 1;
	
}

struct node{
	int i , j;
}d[55 * 55];

inline void bfs(int p , int q)
{
	int head = 0 , tail = 1;
	node now;
	d[tail] = (node){p , q};
	vis[getid(p , q)] = 1;
	while (head < tail)
	{
		now = d[++head];
		int i = now.i , j = now.j , l = j + 1;
		while (mp[i][l] && !vis[getid(i , l)])
			d[++tail] = (node){i , l} , vis[getid(i , l)] = 1 , add(getid(i , l) , getid(i , j)) , l++;
		l = j - 1;
		while (mp[i][l] && !vis[getid(i , l)]) 
			d[++tail] = (node){i , l} , vis[getid(i , l)] = 1 , add(getid(i , l) , getid(i , j)) , l--;
		l = i + 1;
		while (mp[l][j] && !vis[getid(l , j)])
			d[++tail] = (node){l , j} , vis[getid(l , j)] = 1 , add(getid(l , j) , getid(i , j)) , l++;
		l = i - 1;
		while (mp[l][j] && !vis[getid(l , j)]) 
			d[++tail] = (node){l , j} , vis[getid(l , j)] = 1 , add(getid(l , j) , getid(i , j)) , l--;
	}
}

int main()
{
	scanf("%d%d" , &n , &m);
	char s[55];
	for(register int i = 1; i <= n; i++)
	{
		scanf("%s" , s);
		for(register int j = 0; j < m; j++)
			mp[i][j + 1] = (s[j] == '.' ? 1 : 0);
	}
	for(register int i = 1; i <= n; i++)
	{
		int flag = 0;
		for(register int j = 1; j <= m; j++)
		if (mp[i][j] == 1)
		{
			int s = 0 , ss = 0;
			if (mp[i + 1][j] || mp[i - 1][j]) s = 1;
			if (mp[i][j - 1] || mp[i][j + 1]) ss = 1;
			if (s && ss);
			else rt = getid(i , j) , bfs(i , j) , flag = 1;
			if (flag) break;
		}
		if (flag) break;
	}
	memset(vis , 0 , sizeof vis);
	dfs(rt);
	printf("%d" , min(f[rt][1] , f[rt][2]));
}