misschuer

常用链接

统计

积分与排名

百事通

最新评论

zoj 1002 Fire Net

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
  1#include <iostream>
  2#include <queue>
  3#define M 6
  4using namespace std;
  5
  6typedef 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
 13priority_queue <point> Q;
 14char str[ M ][ M ];
 15int n , cnt;
 16
 17void 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
 48void 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
 62void 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
 85void 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
100int 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 此最相思 阅读(236) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理