Patisserie ACM (AOJ1185)

通した.↓ネタバレ
冷静に考えると,こんな感じf:id:sigma425:20150604185824j:plainの赤のところで切る必要は全くない.ちゃんと考えると,切るところの少なくとも片方の端っこの点は,"周りにチョコが3つある"を満たさなければ切る意味が無い.つまり答えは"周チ3"点の数以下になる.逆に,"周チ3"点は切り始めの端っこにならなければいけないこともわかる(切らなきゃダメなのは当たり前で,そのとき端っこになるのも当たり前).これより減るのか,というと,つまり両端が"周チ3"ならお得ですよね,という話.f:id:sigma425:20150604190555j:plain(sampleのやつ,青は"周チ3",他カラフルな線がお得なやつ).全格子点に対し,
お得線は(短点も含めて)それぞれ交わってはいけない.→独立集合
そこを通るお得線は高々2つかつ,2つなら縦と横1つずつになる.→二部グラフじゃん,フロー流して終わり.
フローに気づけばあとは500点レベル.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
const int MAX_V=10000;
int V;				//substitute!!
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];
void add_edge(int u,int v){
	//printf("%d->%d\n",u,v);
	G[u].push_back(v);
	G[v].push_back(u);
}
bool dfs(int v){
	used[v]=true;
	rep(i,G[v].size()){
		int u=G[v][i],w=match[u];
		if(w<0 || (!used[w] && dfs(w))){
			match[v]=u;
			match[u]=v;
			return true;
		}
	}
	return false;
}
int nibu(){
	int res=0;
	memset(match,-1,sizeof(match));
	rep(v,V){
		if(match[v]<0){
			memset(used,0,sizeof(used));
			if(dfs(v)) res++;
		}
	}
	return res;
}
int H,W;
string st[100];
bool s[100][100];
int vc[100][100];
bool is3(int x,int y){
	return (int)(s[x][y])+(int)(s[x+1][y])+(int)(s[x][y+1])+(int)(s[x+1][y+1])==3;
}
bool is4(int x,int y){
	return (int)(s[x][y])+(int)(s[x+1][y])+(int)(s[x][y+1])+(int)(s[x+1][y+1])==4;
}
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main(){
	while(true){
		int ans=1,cnt=0;
		cin>>H>>W;
		if(H==0) break;
		V=H*W;
		rep(i,V) G[i].clear();
		rep(i,H) rep(j,W) vc[i][j]=-1;
		rep(i,H) cin>>st[i];
		rep(i,H) rep(j,W) s[i][j]=(st[i][j]=='#');
		rep(i,H-1) rep(j,W-1){
			if(!is3(i,j)) continue;
			ans++;
			int d_[2];
			if(!s[i+1][j+1]) d_[0]=2,d_[1]=3;
			if(!s[i+1][j]) d_[0]=2,d_[1]=1;
			if(!s[i][j+1]) d_[0]=0,d_[1]=3;
			if(!s[i][j]) d_[0]=0,d_[1]=1;
//			printf("i,j=(%d,%d)\n",i,j);
			rep(h,2){
				int d=d_[h];
				if(d>=2) continue;
				int x=i,y=j;
				x+=dx[d],y+=dy[d];
				while(0<=x&&x<H-1&&0<=y&&y<W-1){
					if(is3(x,y)){
						//show(x);
						//show(y);
						//show(d);
						bool is=0;
						switch(d){
							case 0:
								if(!s[x+1][y+1]||!s[x+1][y]) is=1;
								break;
							case 1:
								if(!s[x+1][y+1]||!s[x][y+1]) is=1;
								break;
						}
						if(!is) break;
						int ii=i,jj=j;
						if(vc[ii][jj]>=0) add_edge(vc[ii][jj],cnt);
						else vc[ii][jj]=cnt;
						while(true){
							ii+=dx[d],jj+=dy[d];
							if(vc[ii][jj]>=0) add_edge(vc[ii][jj],cnt);
							else vc[ii][jj]=cnt;
							if(ii==x&&jj==y) break;
						}
						cnt++;
						break;
					}else if(!is4(x,y)){
						break;
					}
					x+=dx[d],y+=dy[d];
				}
			}
		}
//		show(ans);
		cout<<ans-cnt+nibu()<<endl;
	}
}