提交记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=1<<29,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,s,t,tot,ans,a[105][105];
int h[N],h2[N],dep[N];
struct Edge{
	int to,nxt,cap,flow;
}e[N<<1];
void add(int u,int v,int w){
	e[tot].to=v,e[tot].nxt=h[u],e[tot].cap=w;
	h[u]=tot++;
	e[tot].to=u,e[tot].nxt=h[v];
	h[v]=tot++;
}
int bfs(){
	queue<int>q;
	q.push(s),memset(dep,0,sizeof(dep)),dep[s]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=h[u];~i;i=e[i].nxt){
			int v=e[i].to;
			if(!dep[v]&&e[i].cap>e[i].flow)
				dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int flow){
	if(u==t||!flow)
		return flow;
	int sum=0;
	for(int& i=h2[u];~i;i=e[i].nxt){
		int v=e[i].to,d;
		if(dep[v]==dep[u]+1){
			d=dfs(v,min(flow-sum,e[i].cap-e[i].flow));
			sum+=d,e[i].flow+=d,e[i^1].flow-=d;
			if(sum==flow)
				break;
		}
	}
	return sum;
}
signed main(){
	scanf("%lld%lld",&n,&m),t=N-1;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%lld",&a[i][j]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==1)
				add(s,i*n+j,inf);
			if(a[i][j]==2)
				add(i*n+j,t,inf);
			for(int k=0;k<4;k++){
				int x=i+dx[k],y=j+dy[k];
				if(x<=n&&y<=n&&x>=1&&y>=1)
					add(i*n+j,x*n+y,1);
			}
		}
	}
	while(bfs()){
		memcpy(h2,h,sizeof(h));
		ans+=dfs(s,inf);
	}
	printf("%lld",ans);
	return 0;
}