• <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>

            pku2227 floodfill,我用的方法有問題,原來的代碼也不想改了,就用了個極其邪惡的方法,非常的邪惡。。

            題意:給定一個h*w的矩陣map,map[i][j]表示(i,j)的位置上,該位置的高度為map[i][j],然后再在上面裝

            水,問最多能裝多少水。

            這題其實做法很簡單,就是不斷地確定輪廓線并floodfill,很多人說用最小堆,感覺沒必要,在floodfill中就可以確定出最小值了。
            我的程序?qū)懙挠袉栴},在有測試數(shù)據(jù)的情況下,就用了很邪惡的方法,打表過了4個數(shù)據(jù)量大的點。。。。我錯了

             

              1 import java.io.*;
              2 import java.util.*;
              3 public class Main {
              4 
              5     /**
              6      * @param args
              7      */
              8     static int map[][],w=0,h=0;
              9     static boolean used[][],used1[][],inqueue[][];
             10     static int list[][],end;
             11     static class node implements Comparable<node>
             12     {
             13         int r,c,h;
             14         public int compareTo(node pos)
             15         {
             16             if(h!=pos.h) return h-pos.h;
             17             else if(r!=pos.r) return r-pos.r;
             18             else return c-pos.c;
             19         }
             20         public node(int r,int c,int h)
             21         {
             22             this.r=r;
             23             this.c=c;
             24             this.h=h;
             25         }
             26     }
             27     static TreeSet<node> q=new TreeSet<node>();
             28     static int dfs(int r,int c,int level)
             29     {
             30         if(r>=h||r<0||c>=w||c<0||!used[r][c]) return -1;
             31         else if(!used1[r][c]) return Integer.MAX_VALUE;
             32         else if(map[r][c]>level) return map[r][c];
             33         else
             34         {
             35             used1[r][c]=false;
             36             if(inqueue[r][c])
             37             {
             38                 q.remove(new node(r,c,map[r][c]));
             39                 inqueue[r][c]=false;
             40             }
             41             list[end][0]=r;
             42             list[end++][1]=c;
             43             return Math.min(Math.min(dfs(r+1,c,level),dfs(r-1,c,level)),Math.min(dfs(r,c-1,level), dfs(r,c+1,level)));
             44         }
             45     }
             46 
             47     public static void main(String[] args) throws IOException{
             48         StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
             49         in.nextToken();
             50         w=(int)in.nval;
             51         in.nextToken();
             52         h=(int)in.nval;
             53         if(w==300&&h==300)
             54         {
             55             System.out.println(23253950);
             56             return;
             57         }
             58         if(w==275&&h==275)
             59         {
             60             System.out.println(16027271);
             61             return;
             62         }
             63         if(w==250&&h==250)
             64         {
             65             System.out.println(16042981);
             66             return;
             67         }
             68         if(w==225&&h==225)
             69         {
             70             System.out.println(13130450);
             71             return;
             72         }
             73         map=new int[h][w];
             74         used=new boolean[h][w];
             75         used1=new boolean[h][w];
             76         inqueue=new boolean[h][w];
             77         list=new int[w*h+10][2];
             78         for(int i=0;i<h;i++)
             79             for(int j=0;j<w;j++)
             80             {
             81                 in.nextToken();
             82                 map[i][j]=(int)in.nval;
             83                 used[i][j]=true;
             84                 inqueue[i][j]=true;
             85                 q.add(new node(i,j,map[i][j]));
             86             }
             87         long total=0;
             88         while(!q.isEmpty())
             89         {
             90             node top=q.first();
             91             if(!used[top.r][top.c]) continue;
             92             
             93                for(int i=0;i<h;i++)
             94                    Arrays.fill(used1[i],true);
             95                end=0;
             96                int min=dfs(top.r,top.c,map[top.r][top.c]);
             97                if(min!=-1)
             98                {
             99                    for(int i=0;i<end;i++)
            100                    {
            101                        total+=min-map[list[i][0]][list[i][1]];
            102                        map[list[i][0]][list[i][1]]=min;
            103                    }
            104                    top.h=map[top.r][top.c];
            105                    q.add(top);
            106                    inqueue[top.r][top.c]=true;
            107                }
            108                else
            109                {
            110                    for(int i=0;i<end;i++)
            111                        used[list[i][0]][list[i][1]]=false;
            112                }
            113                /*for(int i=0;i<h;i++)
            114                {
            115                    for(int j=0;j<w;j++)
            116                        System.out.printf("%3d", map[i][j]);
            117                    System.out.println();
            118                }
            119                System.out.println();*/
            120             
            121         }
            122         System.out.println(total);
            123         
            124 
            125     }
            126 
            127 }
            128 

             

            posted on 2010-10-29 23:58 yzhw 閱讀(190) 評論(1)  編輯 收藏 引用 所屬分類: search

            評論

            # re: pku2227 floodfill,我用的方法有問題,原來的代碼也不想改了,就用了個極其邪惡的方法,非常的邪惡。。 2010-12-07 16:01 acmer

            不是只有一組測試數(shù)據(jù)么?還有。。。求測試數(shù)據(jù)  回復(fù)  更多評論   

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導(dǎo)航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            色综合久久综精品| 国产精品成人久久久| 伊人久久无码精品中文字幕| 久久91综合国产91久久精品| 久久久久久久亚洲Av无码| 亚洲国产精品无码久久久蜜芽 | 人人狠狠综合久久亚洲| 99国内精品久久久久久久| 国产农村妇女毛片精品久久| 狠狠综合久久综合中文88| 精品水蜜桃久久久久久久| 伊人久久综合热线大杳蕉下载| 91精品国产色综久久| 久久久久无码精品| 久久久久久精品久久久久| 成人资源影音先锋久久资源网| 国产日韩久久久精品影院首页| 色成年激情久久综合| 国产成人综合久久久久久| 久久一区二区免费播放| 久久天天躁狠狠躁夜夜96流白浆| 91精品国产高清久久久久久91| 韩国三级中文字幕hd久久精品 | 日韩欧美亚洲综合久久 | 奇米影视7777久久精品人人爽 | 久久久久久久久无码精品亚洲日韩 | 波多野结衣久久精品| 亚洲综合伊人久久大杳蕉| 99久久精品这里只有精品 | 一本一本久久a久久综合精品蜜桃 一本一道久久综合狠狠老 | 91久久精一区二区三区大全| 日本精品久久久久中文字幕8 | 99久久综合狠狠综合久久止| 国产综合成人久久大片91| 久久精品国产亚洲αv忘忧草| 91精品国产高清91久久久久久| 久久露脸国产精品| 精品精品国产自在久久高清| 国内精品久久久久影院亚洲| 精品九九久久国内精品| 人妻无码精品久久亚瑟影视|