Algoogle

Algorithm for Programming Contest

AOJ 1185 Patisserie ACM

Category: AOJ Tag: bipartite-matching

Patisserie ACM

問題概要


解法


凹になっている角に注目する.
凹になっている角を通るように切ればとりあえず長方形になるように切れるから.
その時一つの凹な角だけでなく, 2つの凹な角を通るように切れば効率がいい.

aoj1185-01

凹な角から垂直, もしくは水平に線を伸ばして, 凹になっている角にぶつかるような線分をリストアップする.
それらの線分で交わるものに辺を張ったものは2部グラフになる(縦と横の線しかないから)ので その最大マッチング問題を解く.
その値を2部グラフの頂点数から引けば, 一緒に切られた凹な角の数がわかるので
よってカット回数は凹な角の総数からこれを引いてやればいい.
求めるのはピースの数なので最後に+1をする.

コード


(1185.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define pb push_back

typedef vector<int> vi;

struct Line{
    bool tate;
    int sx, sy, tx, ty;
    Line(int sx, int sy, int tx, int ty, bool tate):
	sx(sx),sy(sy),tx(tx),ty(ty),tate(tate){}
};

int h, w;
vector<vi> choco;
vector<Line> lines;

const int MAX_V = 1000000;
int  V;
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v){
    G[u].push_back(v);
    G[v].push_back(u);
}

bool dfs(int v){
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
	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 bipartie_matching(){
    int res = 0;
    memset(match, -1, sizeof(match));
    for(int v = 0; v < V; v++){
	if(match[v] < 0){
	    memset(used, 0, sizeof(used));
	    if(dfs(v)){
		res++;
	    }
	}
    }
    return res;
}

void make_line(){
    rep(i,h-1){
	rep(j,w-1){
	    //yoko
	    if((!choco[i][j] && choco[i+1][j] && choco[i][j+1] && choco[i+1][j+1]) ||
	       (choco[i][j] && !choco[i+1][j] && choco[i][j+1] && choco[i+1][j+1])){
		repi(x,j,w-1){
		    if((choco[i][x] && choco[i+1][x] && !choco[i][x+1] && choco[i+1][x+1]) ||
				 (choco[i][x] && choco[i+1][x] && choco[i][x+1] && !choco[i+1][x+1])){
			lines.pb(Line(j,i,x,i,0));
			break;
		    }
		    if(choco[i][x] && choco[i+1][x] && !choco[i][x+1] && !choco[i+1][x+1]) break;
		}
	    }
	    //tate
	    if((!choco[i][j] && choco[i+1][j] && choco[i][j+1] && choco[i+1][j+1]) ||
	       (choco[i][j] && choco[i+1][j] && !choco[i][j+1] && choco[i+1][j+1])){
		repi(y,i,h-1){
		    if((choco[y][j] && !choco[y+1][j] && choco[y][j+1] && choco[y+1][j+1]) ||
				 (choco[y][j] && choco[y+1][j] && choco[y][j+1] && !choco[y+1][j+1])){
			lines.pb(Line(j,i,j,y,1));
			break;
		    }
		    if(choco[y][j] && !choco[y+1][j] && choco[y][j+1] && !choco[y+1][j+1]) break;
		}
	    }
	}
    }
}

void init(){
    choco.clear();
    choco.resize(h,vi(w));
    rep(i,MAX_V) G[i].clear();
    lines.clear();
}

bool crossline(Line l1, Line l2){
    if(l1.tate == l2.tate) return false;

    if(l2.tate) swap(l1,l2);
    if((l1.sy <= l2.sy && l1.ty >= l2.sy) &&
       (l2.sx <= l1.sx && l2.tx >= l1.sx)) return true;
    return false;
}

int corner(){
    int ret = 0;
    rep(i,h-1)rep(j,w-1){
	if((!choco[i][j] && choco[i+1][j] && choco[i][j+1] && choco[i+1][j+1]) ||
	   (choco[i][j] && !choco[i+1][j] && choco[i][j+1] && choco[i+1][j+1]) ||
	   (choco[i][j] && choco[i+1][j] && !choco[i][j+1] && choco[i+1][j+1]) ||
	   (choco[i][j] && choco[i+1][j] && choco[i][j+1] && !choco[i+1][j+1])) ret++;
    }
    return ret;
}

int main(){
    while(cin >> h >> w, h || w){
	init();
	rep(i,h)rep(j,w){
	    char c;
	    cin >> c;
	    if(c == '#') choco[i][j] = 1;
	    else choco[i][j] = 0;
	}
	make_line();
	rep(i,lines.size())repi(j,i+1,lines.size()){
	    if(crossline(lines[i],lines[j])) add_edge(i,j);
	}
	V = lines.size();
	cout << corner() - lines.size() + bipartie_matching() + 1 << endl;
    }
    return 0;
}

Comments