題意：給定一個(gè)h*w的矩陣map，map[i][j]表示（i，j）的位置上，該位置的高度為map[i][j]，然后再在上面裝
水，問(wèn)最多能裝多少水。
這題其實(shí)做法很簡(jiǎn)單，就是不斷地確定輪廓線并floodfill，很多人說(shuō)用最小堆，感覺(jué)沒(méi)必要，在floodfill中就可以確定出最小值了。
我的程序?qū)懙挠袉?wèn)題，在有測(cè)試數(shù)據(jù)的情況下，就用了很邪惡的方法，打表過(guò)了4個(gè)數(shù)據(jù)量大的點(diǎn)。。。。我錯(cuò)了
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