Patisserie ACM (AOJ1185)
通した.↓ネタバレ
冷静に考えると,こんな感じの赤のところで切る必要は全くない.ちゃんと考えると,切るところの少なくとも片方の端っこの点は,"周りにチョコが3つある"を満たさなければ切る意味が無い.つまり答えは"周チ3"点の数以下になる.逆に,"周チ3"点は切り始めの端っこにならなければいけないこともわかる(切らなきゃダメなのは当たり前で,そのとき端っこになるのも当たり前).これより減るのか,というと,つまり両端が"周チ3"ならお得ですよね,という話.(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; } }