AOJ1185 Patisserie ACM

問題

Patisserie ACMACM洋菓子店 | Aizu Online Judge

感想

面白いですねこれ。(ほんとに感想)

一見して何もわからないけれど。すっごく簡単に言うと。

• 折るということについて考える(必要条件・共通項を見つける)と凹みのところが大事な点(2*2の範囲のうち3個がチョコのところ)とわかる

• (最適について考えると)大事な点が(垂直・水平な)線で結べると嬉しい + 交差していると無理 　がわかる

• グラフに置き換えると独立集合の問題に変わる + 二分グラフとなる

• 二部マッチングで解ける。

という感じ。

大事な点に関しては、折り目はチョコを折る時は必ずその点を通る直線になっていること、という話ですね。

その次が、答えがすべての大事な点をカバーできる直線の数 + 1になるわけなんですが、一つの直線で二つの点をカバーできると嬉しいねという話

実装はそんなにむつかしくないし時間も厳しくないので適当にやりました。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;
typedef complex<double> point;

struct segment : public vector<point> {
	segment(const point &a, const point &b) {
		push_back(a); push_back(b);
	}
};

double cross(const point& a, const point& b) {
	return imag(conj(a)*b);
}

double dot(const point& a, const point& b) {
	return real(conj(a)*b);
}

int ccw(point a, point b, point c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;       // counter clockwise
	if (cross(b, c) < 0)   return -1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	return 0;
}

bool intersectSS(const segment &s, const segment &t) {
	return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) <= 0 &&
		ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) <= 0;
}


char mp[111][111];
bool check[111][111];

int h,w;

#define MAX_V 22222
vector<int> v[MAX_V];
int match[MAX_V];
bool used[MAX_V];
vector<segment> segs;

void add_edge(int a,int b){
	v[a].PB(b);
	v[b].PB(a);
}

bool matchdfs(int a){
	used[a] = true;
	for(int i = 0;i < v[a].size();i++)	{
		int u = v[a][i],w = match[u];
		if(w < 0 || !used[w] && matchdfs(w)){
			match[u] = a;
			match[a] = u;
			return true;
		}
	}
	return false;
}

//二部マッチング
int two_matching_max(int l){
	int res = 0;
	memset(match,-1,sizeof(match));
	REP(v,l){
		if(match[v] < 0){
			memset(used,0,sizeof(used));
			if(matchdfs(v))res++;
		}
	}
	return res;
}

bool isOUT(int y,int x){
	if(x < 0 || y < 0 || x >= w || y >= h)return true;
	return false;
}

int main(){
	
	while(cin >> h >> w,h|w){
		int checkcount = 0;
		REP(i,MAX_V)v[i].clear();
		segs.clear();
		REP(i,111)REP(j,111)check[i][j] = false;
		REP(i,111)REP(j,111)mp[i][j] = '.';
		
		REP(i,h)REP(j,w)cin >> mp[i][j];
		
		REP(i,h-1){
			REP(j,w-1){
				int cou = 0;
				REP(x,2)REP(y,2)if(mp[i+y][j+x] == '#')cou++;
				if(cou == 3){
					checkcount++;
					check[i][j] = true;
				}
			}
		}
		
		REP(i,h-1){
			REP(j,w-1){
				if(check[i][j]){
					int y = i + 1;
					int x = j;
					while(1){
						if(isOUT(y,x))break;
						if(mp[y][x] != '#' || mp[y][x+1] != '#')break;
						if(check[y][x]){
							segs.PB(segment(point(i,j),point(y,x)));
							break;
						}
						y++;
					}
					DBG(cout << "!" << endl;)
					y = i;
					x = j + 1;
					while(1){
						if(isOUT(y,x))break;
						if(mp[y][x] != '#' || mp[y+1][x] != '#')break;
						if(check[y][x]){
							segs.PB(segment(point(i,j),point(y,x)));
							break;
						}
						x++;
					}
				}
			}
		}
		
		REP(i,segs.size()){
			for(int j = i + 1;j < segs.size();j++){
				if(intersectSS(segs[i],segs[j])){
					 add_edge(i,j);
				 }
			}
		}
		
		int ans = checkcount - (segs.size() - two_matching_max(MAX_V)) + 1;
		cout << ans << endl;
		
	}
	
	return 0;
}