• <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中就可以確定出最小值了。
            我的程序寫的有問題,在有測試數據的情況下,就用了很邪惡的方法,打表過了4個數據量大的點。。。。我錯了

             

              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 閱讀(185) 評論(1)  編輯 收藏 引用 所屬分類: search

            評論

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

            不是只有一組測試數據么?還有。。。求測試數據  回復  更多評論   

            <2025年5月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久国产福利免费| 亚洲国产精品无码久久| 欧美精品一本久久男人的天堂| 久久久久人妻一区二区三区vr| 久久精品国产免费| 久久毛片一区二区| 久久99国产精一区二区三区| 久久亚洲2019中文字幕| 久久亚洲日韩精品一区二区三区| 精品无码久久久久国产| 午夜精品久久久久久| 成人久久精品一区二区三区| 日本久久中文字幕| 国产综合久久久久| 久久亚洲国产精品成人AV秋霞| 狠狠色丁香久久婷婷综| 亚洲中文字幕久久精品无码APP| 精品久久综合1区2区3区激情| 久久夜色精品国产噜噜麻豆| 免费精品国产日韩热久久| 国产精品成人无码久久久久久| 无码人妻少妇久久中文字幕蜜桃 | 国内精品久久国产大陆| 日本加勒比久久精品| 亚洲综合精品香蕉久久网97| 人妻无码久久一区二区三区免费 | 久久亚洲国产成人精品无码区| 国内精品人妻无码久久久影院| 伊人色综合久久天天人手人婷 | 亚洲欧洲久久av| 久久精品成人免费观看97| 国产精品99久久精品爆乳| 国产午夜久久影院| 国产精品久久久久久搜索 | 丰满少妇人妻久久久久久4| 99久久99这里只有免费费精品| 97视频久久久| 亚洲AV无码1区2区久久| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 成人a毛片久久免费播放| 国产精品欧美久久久久天天影视|