misschuer

公告

留言簿

隨筆分類

文章分類

acm (rss)
Java (rss)

隨筆檔案

文章檔案

2009年4月 (1)

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 61
文章 - 1
評論 - 18
引用 - 0

積分與排名

積分 - 24987
排名 - 727

百事通

hao123
WPL
杭電
松松
星和

zoj 1002 Fire Net

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
1

#include <iostream>
2

#include <queue>
3

#define M 6
4

using namespace std;
5

6

typedef struct point{
7

int i , j, cnt;
8

friend bool operator < (point a, point b){
9

return a.cnt < b.cnt;
10

}
11

}point;
12

13

priority_queue <point> Q;
14

char str[ M ][ M ];
15

int n , cnt;
16

17

void endeavor (int x , int y){
18

//a point has four directions
19

//for each piont we could divide into five Situations: None direct has wall , One

, Two

,Three

, Four

;
20

int i , j;
21

cnt = 0;
22

for (i = y + 1;i < n;++ i){
23

if (str[ x ][ i ] == 'X'){
24

cnt ++ ; break;
25

}
26

}
27

28

for (i = y - 1;i >= 0;-- i){
29

if (str[ x ][ i ] == 'X'){
30

cnt ++ ; break;
31

}
32

}
33

34

for (i = x + 1;i < n;++ i){
35

if (str[ i ][ y ] == 'X'){
36

cnt ++ ; break;
37

}
38

}
39

40

for (i = x - 1;i >= 0;-- i){
41

if (str[ i ][ y ] == 'X'){
42

cnt ++ ; break;
43

}
44

}
45

46

}
47

48

void init (){
49

point p;
50

for (int i = 0;i < n;++ i){
51

for (int j = 0;j < n;++ j){
52

if (str[ i ][ j ] == '.'){
53

p.i = i; p.j = j;
54

endeavor(i , j);
55

p.cnt = cnt;
56

Q.push(p);
57

}
58

}
59

}
60

}
61

62

void recover (int x , int y){
63

int i , j;
64

for (i = y + 1;i < n;++ i){
65

if (str[ x ][ i ] == 'X') break;
66

str[ x ][ i ] = 'N';
67

}
68

69

for (i = y - 1;i >= 0;-- i){
70

if (str[ x ][ i ] == 'X') break;
71

str[ x ][ i ] = 'N';
72

}
73

74

for (i = x + 1;i < n;++ i){
75

if (str[ i ][ y ] == 'X') break;
76

str[ i ][ y ] = 'N';
77

}
78

79

for (i = x - 1;i >= 0;-- i){
80

if (str[ i ][ y ] == 'X') break;
81

str[ i ][ y ] = 'N';
82

}
83

}
84

85

void GY (){
86

point p;int ans = 0;
87

while (!Q.empty()){
88

p = Q.top();
89

Q.pop();
90

if (str[p.i][p.j] == '.'){
91

ans ++;
92

str[p.i][p.j] = 'O';
93

recover (p.i , p.j);
94

}
95

else continue;
96

}
97

cout << ans << endl;
98

}
99

100

int main(){
101

while (cin >> n && n){
102

for (int i = 0;i < n;++ i){
103

cin >> str[ i ];
104

}
105

init ();
106

GY ();
107

}
108

return 0;
109

}

還有一種可用圖論做

網絡流或者二分圖的最大匹配
對于每行每列的連通塊定義一個不同的編號,然后上面的算法選一個算

posted on 2010-04-24 13:03 此最相思閱讀(250) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品