这样一道算法题，放出来大伙思考思考。_J2SE

这么一道算法题，放出来大伙思考思考。。。
刚看csdn论坛，于是想到大四时听同学说了这么一道题，当时做了几天没搞出来，题目意思如下：

给你一个二维数组（比如是M*N的），把他们放入M*N的方格中，每个数字代表该方格的高度，这样就俯视就会形成凹凸不平，如果用这个形状存储水，凹的地方会有积水，请问它能存储多少水？
例如二维数组为：
9 9 9 9
3 0 0 9
7 8 9 6
时，答案是中间的0,0位置可以存储3（因为其外面最低是3，即“木桶效应”）个单位的水，因此答案为3+3=6

------解决方案--------------------

引用:

Quote: 引用:

我的思路是：
1、每个数字看成是一个对象，该对象有上下左右中五个属性。
2、去除掉，上下左右不全的数字。
3、判断，“中”的是不是最小值，不是则除掉。若是，则取次小值。
4、最终的结果就是，所有次小值的和。

那如果二维数组为：
9 9 9 9 9
9 1 5 1 9
9 5 6 5 9
9 2 5 2 9
9 9 9 9 9
按照你的计算方法，上面数字6就积水为0
实际上它的积水应该是3才对吧

找出这个二维数组形成木桶时最短那块板，木桶的桶高是有这个数组的“四边”所构成，即a[0][0]...a[0][N-1],a[0][N-1]...a[M-1][N-1],a[M-1][N-1]...a[M-1][0],a[M-1][0]...a[0][0],把这些都放进一个数组，然后找出最小的那个数，也就是最短的木板。然后把除了四边的那些数与这个最短的木板作差，负数则能储水；正数刚高于最低桶边，不能储水，无视之
------解决方案--------------------
二维数组图形化
× 代表板块无用
+  代表板块边界
-  代表此板块能盛水
首先图形的四个角为× 板块不可用
          剩余的便为+ 暂时作为边界
          考虑边界内的板块中贴着边界的板块，
if（此板块的值>=边界的值）
    {
      边界+ 变为×；此板块作为边界，变为+
     }
else
    {
       此板块标志为- ，表示该板块能盛水
     }
最后会暂时形成两个结果
1，一个大桶，此时最简单，取该桶最短板，然后与桶内板块比较，获得暂时盛水量
2，多个大桶，分别取桶最短板，然后与桶内板块比较，相加，获得暂时盛水量

这时，第二个问题出现了，大桶内或许还有更深的桶，例如6L所举例

这个时候对桶进行分析，将桶内盛水板块补充为最短边界，这样边界就失效的，继续按照开始所说，
求边界，得到大桶，然后递归分析，直到桶内再没有桶为止
每次取得的暂时盛水量相加，即可得到最终取水量！
------解决方案--------------------


package xj;

public class wood {
	
	public static int woodEffect(int[][] woods,int m,int n){
		int total=0;
		for(int i=1;i<m-1;i++){
			for(int j=1;j<n-1;j++){

				int upnum=woods[i-1][j];
				int downnum=woods[i+1][j];
				int leftnum=woods[i][j-1];
				int rightnum=woods[i][j+1];
				int num=woods[i][j];
				
				int min=99;
				
				int x=i;
				int y=j;
				while(x>0){
					x--;
					if(woods[x][y]>=num){
						upnum=woods[x][y];
					}
				}

				if(min>upnum){
					min=upnum;
				}
				
				x=i;
				y=j;
				while(x<m-1){
					x++;
					if(woods[x][y]>=num){
						downnum=woods[x][y];
					}
				}

				if(min>downnum){
					min=downnum;
				}
				
				x=i;
				y=j;
				while(y>0){
					y--;
					if(woods[x][y]>=num){
						leftnum=woods[x][y];
					}
				}
				
				if(min>leftnum){
					min=leftnum;
				}
				
				x=i;
				y=j;
				
				while(y<n-1){
					y++;
					if(woods[x][y]>=num){
						rightnum=woods[x][y];
					}
				}
				
				if(min>rightnum){
					min=rightnum;
				}
				total+=min-num;

			}

		}
	
		return total;
	}
	
	public static void main(String[] args) {
//		int[][] woods={{9,9,9,9},{3,0,0,9},{7,8,9,6}};
		int[][] woods={{9,9,9,9,9},{9,1,5,1,9},{9,5,6,5,9},{9,2,5,2,9},{9,9,9,9,9}};

		System.out.println(wood.woodEffect(woods,5,5));
		
	}
	
	

}

------解决方案--------------------

引用:

Quote: 引用:

二维数组图形化
× 代表板块无用
+  代表板块边界
-  代表此板块能盛水

                     .
                     .
                     .

最后会暂时形成两个结果
1，一个大桶，此时最简单，取该桶最短板，然后与桶内板块比较，获得暂时盛水量
2，多个大桶，分别取桶最短板，然后与桶内板块比较，相加，获得暂时盛水量

这时，第二个问题出现了，大桶内或许还有更深的桶，例如6L所举例

这个时候对桶进行分析，将桶内盛水板块补充为最短边界，这样边界就失效的，继续按照开始所说，
求边界，得到大桶，然后递归分析，直到桶内再没有桶为止
每次取得的暂时盛水量相加，即可得到最终取水量！

看了半天，后面这段还不是看的很明白啊，解题思路没明确，程序还能实现么？？？

后面这段我举个例子吧
5 2 2 6 6 6 6 6 8 6
5 6 6 5 5 5 5 5 5 6
2 6 5 5 8 8 8 5 5 6
6 5 5 5 8 3 7 5 5 6
5 6 5 5 8 8 7 5 5 6
5 7 5 5 5 5 5 5 5 6
6 6 6 6 6 6 6 6 6 6
经过图形化（无用板块不显示边界显示为数字）
      6 6 6 6 6 8
    6 - - - - - - 6
  6 - - - - - - - 6