• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 此最相思 閱讀(242) 評論(0)  編輯 收藏 引用

            无码人妻少妇久久中文字幕蜜桃| 日本一区精品久久久久影院| 欧美午夜A∨大片久久 | 久久精品国产乱子伦| 国内精品九九久久精品| 久久久亚洲欧洲日产国码二区| 久久不射电影网| 色青青草原桃花久久综合| 久久99精品久久久久子伦| 久久国产福利免费| 久久99国产综合精品女同| 久久婷婷人人澡人人| 久久精品aⅴ无码中文字字幕重口| 91精品婷婷国产综合久久| 久久无码专区国产精品发布| 麻豆精品久久精品色综合| 中文字幕人妻色偷偷久久 | 久久精品国产只有精品66| 久久精品国产亚洲精品2020 | 午夜精品久久久久久久| 久久乐国产精品亚洲综合| 久久精品水蜜桃av综合天堂| 精产国品久久一二三产区区别 | 欧美日韩中文字幕久久久不卡| 999久久久无码国产精品| 人妻无码αv中文字幕久久琪琪布| 麻豆精品久久精品色综合| 大伊人青草狠狠久久| 日韩av无码久久精品免费| 中文字幕热久久久久久久| 日本欧美国产精品第一页久久| 国产激情久久久久影院老熟女| 97久久精品午夜一区二区| 国产精品国色综合久久| 久久久久人妻一区精品色| 欧洲人妻丰满av无码久久不卡| 波多野结衣久久| 久久精品国产日本波多野结衣 | 久久国产精品77777| 久久精品国产亚洲av麻豆色欲| 午夜福利91久久福利|