40pts求助
查看原帖
40pts求助
121813
老子是北瓜楼主2020/12/13 19:26

对着题解改过了,还是不对……

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int n,m,w,sum;
int now[40003];
bool cant[203][203],vis[40003];
vector<vector<int> > g(40003);
int dx[8]={-3,-1,1,3,3,1,-1,-3};
int dy[8]={-1,-3,-3,-1,1,3,3,1};
inline int idx(int x,int y){
	return (x-1)*m+y;
}
bool dfs(int u){
	for(int i=0; i<g[u].size(); ++i)
	{
		int v=g[u][i];
		if(vis[v]==0){
			vis[v]=1;
			if(now[v]==0 || dfs(now[v])==1){
				now[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d",&n,&m,&w);
	int x,y;
	for(int i=1; i<=w; ++i)
	{
		scanf("%d%d",&x,&y);
		cant[x][y]=1;
	}
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j){
			if(cant[i][j] || i&1) continue;
			for(int k=0; k<=7; ++k){
				int sx=i+dx[k];
				int sy=j+dy[k];
				if(sx<1 || sx>n || sy<1 || sy>m || cant[sx][sy])
					continue;
				g[idx(i,j)].push_back(idx(sx,sy));
			}
		}
	}
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j){
			int u=idx(i,j);
			memset(vis,0,sizeof(vis));
			if(dfs(u))
				++sum;
		}
	}
	cout<<n*m-sum-w;
	return 0;
}
2020/12/13 19:26
加载中...