bzoj3175【TJOI2013】攻擊裝置

bzoj3175【TJOI2013】攻擊裝置

Description

給定一個01矩陣，其中你可以在0的位置放置攻擊裝置。每一個攻擊裝置（x,y）都可以按照“日”字攻擊其周圍的 8個位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1), (x+1,y+2),(x+2,y+1)
求在裝置互不攻擊的情況下，最多可以放置多少個裝置。

Input

Output

Sample Input

Sample Output

HINT

100%數據 N<=200 

二分圖最大點獨立集裸題

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 40005
using namespace std;
int n,cnt,ans,head[maxn],match[maxn];
int dx[8]={-1,-2,1,2,-1,-2,1,2},dy[8]={-2,-1,-2,-1,2,1,2,1};
bool f[205][205],vst[maxn];
char s[205];
struct edge_type{int next,to;}e[maxn*8];
inline int num(int x,int y)
{
	return (x-1)*n+y;
}
inline void add_edge(int x,int y)
{
	e[++cnt]=(edge_type){head[x],y};
	head[x]=cnt;
}
inline bool dfs(int x)
{
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if (!vst[y])
		{
			vst[y]=true;
			if (!match[y]||dfs(match[y]))
			{
				match[y]=x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d",&n);
	F(i,1,n)
	{
		scanf("%s",s+1);
		F(j,1,n) f[i][j]=s[j]=='0';
	}
	F(i,1,n) F(j,1,n) if (f[i][j]&&(i+j)%2) F(k,0,7)
	{
		int x=i+dx[k],y=j+dy[k];
		if (x<1||y<1||x>n||y>n) continue;
		if (!f[x][y]) continue;
		add_edge(num(i,j),num(x,y));
	}
	F(i,1,n) F(j,1,n) if (f[i][j]) ans++;
	F(i,1,n) F(j,1,n) if (f[i][j]&&(i+j)%2)
	{
		memset(vst,false,sizeof(vst));
		if (dfs(num(i,j))) ans--;
	}
	printf("%d\n",ans);
	return 0;
}