思路

注：上图只是个例子，其实建图时 \(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]));

}
巴特西

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

思路

\(Code\)

最新文章

热门文章
