求助 ： 和木桶原理有关的开发问题

Question

木桶原理 二维数组

Answer 1

public class TestMain {
public static void main(String[] args) {
int[] numbers_one = new int[]{12,14,12,44,14,25};
int[] numbers_two = new int[]{23,0,0,0,0,55};
int[] numbers_three = new int[]{7,45,22,23,24,35};
//测试数据
Queue<int[]> data = new LinkedList<int[]>();
data.add(numbers_one);
data.add(numbers_two);
data.add(numbers_three);

//最小值
int min = -1;
//行数计数器
int count = 0;
while(data.size() != 0){
//第一行和最后一行
if(count == 0 || data.size() == 1){
//获得一行的数据
int[] numbers = data.poll();
//将每一个数字和最小值比较
for(int number : numbers){
//初始时不判断，直接设置为最小值
if(min == -1){
min = number;
}else {
//设置最小值
min = TestMain.getMinNumbers(min, number);
}
}
}
//中间的数据
else{
//获得一行的数据
int[] numbers = data.poll();

//第一个数据
int head = numbers[0];
//设置最小值
min = TestMain.getMinNumbers(min, head);

//最后一个数据
int end = numbers[numbers.length - 1];
//设置最小值
min = TestMain.getMinNumbers(min, end);
}

count++;
}

System.out.println("最低的木板高度是:" + min);
}

/**
 * 获得两个数中的最小数
 * @param min
 * @param number
 * @return
 */
public static int getMinNumbers(int min,int number){
return min < number ? min : number; 
    }
}

Answer 2

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={{3,3,3,3,3},{3,1,3,3,3},{3,3,2,3,3},{3,3,3,3,3}};
int[][] woods={{5,5,5,5,5,5,5},{5,5,3,3,3,5,5},{5,5,3,4,3,5,5},{5,5,3,3,3,5,5},{5,5,5,5,5,5,5}};
System.out.println(wood.woodEffect(woods,5,7));

}

Answer 3

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={{3,3,3,3,3},{3,1,3,3,3},{3,3,2,3,3},{3,3,3,3,3}};
int[][] woods={{5,5,5,5,5,5,5},{5,5,3,3,3,5,5},{5,5,3,4,3,5,5},{5,5,3,3,3,5,5},{5,5,5,5,5,5,5}};
System.out.println(wood.woodEffect(woods,5,7));

}
当数组改为下面的时候
{{3,3,3,3,3},{3,2,2,2,3},{3,3,3,2,3},{3,2,2,2,3},{3,3,3,3,3}}
运行结果为3，但实际上应为0

Answer 4

先贴代码
package com.cch.waterhole;import java.util.HashMap;
import java.util.Map;public class MainClass {
public static void main(String[] args) {
MainClass caculate=new MainClass(6,7);
caculate.printHeight();
caculate.tellNeighbour(0, 0, 0);
System.out.println("------------------------------");
caculate.printWaterH();
System.out.println("------------------------------");
System.out.println("总共可以装："+caculate.getWater());
}

public MainClass(){
this(10,10);
}

public MainClass(int m,int n){
if(m<3||n<3){
System.out.println("给定值的太小");
m=3;
n=3;
}
this.m=m;
this.n=n;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
Block tempBlock=new Block(i, j);
tempBlock.setHeight((int) (Math.random()*10));
if(i==0||j==0||i==m-1||j==n-1){
tempBlock.setWall(true);
}
data.put(i+","+j, tempBlock);
}
}
}

public void tellNeighbour(int x,int y,int height){
Block tempBlock=data.get(x+","+y);
if(tempBlock==null){
return;
}
if(tempBlock.isWall()||height<tempBlock.getHeight()){
if(tempBlock.getTellState()){
return;
}
tempBlock.setTellState(true);
tempBlock.setWall(true);
height=tempBlock.getHeight();
tellNeighbour(x+1,y,height);
tellNeighbour(x,y-1,height);
tellNeighbour(x-1,y,height);
tellNeighbour(x,y+1,height);
}else {
if(height<tempBlock.getWaterH()){
tempBlock.setWaterH(height);
tellNeighbour(x+1,y,height);
tellNeighbour(x,y-1,height);
tellNeighbour(x-1,y,height);
tellNeighbour(x,y+1,height);
}
}
}

public void printHeight(){
for(int i=0;i<this.m;i++){
for(int j=0;j<this.n;j++){
Block tempBlock=data.get(i+","+j);
System.out.print(tempBlock.getHeight()+"  "); 
}
System.out.println();
}
}
public void printWaterH(){
for(int i=0;i<this.m;i++){
for(int j=0;j<this.n;j++){
Block tempBlock=data.get(i+","+j);
if(tempBlock.isWall()){
System.out.print(tempBlock.getHeight()+". "); 
}else{
System.out.print(tempBlock.getHeight()); 
System.out.print(tempBlock.getWaterH()+" "); 
}
}
System.out.println();
}
}
public int getWater(){
int sum=0;
for(int i=0;i<this.m;i++){
for(int j=0;j<this.n;j++){
Block tempBlock=data.get(i+","+j);
if(!tempBlock.isWall()){
sum+=tempBlock.getWaterH()-tempBlock.getHeight(); 
}
}
}
return sum;
}
private int m;
private int n;
private Map<String,Block> data=new HashMap<String, Block>();
}class Block{
private int x;
private int y;
private int height;
private int waterH;
private boolean wall;
private boolean tellState;

public Block(int x,int y){
this.x=x;
this.y=y;
waterH=100;
tellState=false;
wall=false;
}

public int getX() {
return x;
} public int getY() {
return y;
} public int getHeight() {
return height;
} public void setHeight(int height) {
this.height = height;
} public int getWaterH() {
return waterH;
} public void setWaterH(int waterH) {
this.waterH = waterH;
} public boolean isWall() {
return wall;
} public void setWall(boolean wall) {
this.wall = wall;
} public boolean getTellState() {
return tellState;
} public void setTellState(boolean tellState) {
this.tellState = tellState;
}
}

Answer 5

http://bbs.csdn.net/topics/390712018重复问题。

Answer 6

通过目前所有测试用例的一种实现方法：import java.util.Scanner;public class Cannikin { // 木桶            static int M            = 0; // 行：有效范围[0,M)
            static int N            = 0; // 列：有效范围[0,N)
    final   static int GRID_HEIGHT  = 0; // 方格属性下标0：方格高度
    final   static int GRID_WATER   = 1; // 方格属性下标1：储存水量
            static int[][][] gridArray;  // 方格二维数组：M行 * N列 * 方格属性
            static int maxHeight    = 0; // 方格高度最大值    final   static int INVALID_VALUE = -1; // 无效值    public static void main(String[] args) {
        preprocess();               // 预处理
        addWater();                 // 加满水
        while (removeWater()) { }   // 移除水（直到无法再移除任何方格的水时停止）
        postprocess();              // 后处理
    }    private static void preprocess() { // 预处理
        System.out.println("请输入方格二维数组的行数：");
        do {
            try {
                M = (new Scanner(System.in)).nextInt();
            } catch(Exception e) {
                M = INVALID_VALUE;
            }
        } while(M == INVALID_VALUE);        System.out.println("请输入方格二维数组的列数：");
        do {
            try {
                N = (new Scanner(System.in)).nextInt();
            } catch(Exception e) {
                N = INVALID_VALUE;
            }
        } while(N == INVALID_VALUE);        // 方格二维数组初始化
        System.out.println("请输入方格二维数组的数值：");
        gridArray = new int[M][N][GRID_WATER + 1];
        for (int m = 0; m < M; m++) {
            for (int n = 0; n < N; n++) {
                do {
                    try {
                        gridArray[m][n][GRID_HEIGHT] = (new Scanner(System.in)).nextInt();
                    } catch(Exception e) {
                        gridArray[m][n][GRID_HEIGHT] = INVALID_VALUE;
                    }
                } while(gridArray[m][n][GRID_HEIGHT] == INVALID_VALUE);
                gridArray[m][n][GRID_WATER]     = 0;
            }
        }        printArray(GRID_HEIGHT);
    }    private static void addWater() { // 加满水
        // 方格高度最大值设定
        for (int m = 0; m < M; m++) {
            for (int n = 0; n < N; n++) {
                if (maxHeight < gridArray[m][n][GRID_HEIGHT]) {
                    maxHeight = gridArray[m][n][GRID_HEIGHT];
                }
            }
        }        // 加满水
        for (int m = 0; m < M; m++) {
            for (int n = 0; n < N; n++) {
                gridArray[m][n][GRID_WATER] = maxHeight - gridArray[m][n][GRID_HEIGHT];
            }
        }
        System.out.print("加满水后，");
        printArray(GRID_WATER);
    }    private static boolean removeWater() { // 移除水
        for (int m = 0; m < M; m++) {
            for (int n = 0; n < N; n++) {
                if (canRemoveWater(m, n)) { // 还能移除水
                    System.out.print("移除水后，");
                    printArray(GRID_WATER);
                    return true; // 继续尝试移除水
                }
            }
        }
        return false; // 直到无法再移除任何方格的水时停止
    }    private static boolean canRemoveWater(final int m, final int n) { // 能否移除水
        boolean returnValue = false;        if (gridArray[m][n][GRID_WATER] > 0) { // 有水才有可能移除
            if (m == 0 || m == M -1 || n == 0 || n == N -1) { // 边界上的水都可以移除
                gridArray[m][n][GRID_WATER] = 0;
                returnValue = true;
            } else { // 非边界上的,如果高于周围的水都可以移除
                if (gridArray[m  ][n  ][GRID_WATER] + gridArray[m  ][n  ][GRID_HEIGHT] >
                    gridArray[m-1][n  ][GRID_WATER] + gridArray[m-1][n  ][GRID_HEIGHT]) { // 上
                    gridArray[m  ][n  ][GRID_WATER] =
                    gridArray[m-1][n  ][GRID_WATER] + gridArray[m-1][n  ][GRID_HEIGHT]
                                                    - gridArray[m  ][n  ][GRID_HEIGHT];
                    if (gridArray[m  ][n  ][GRID_WATER] < 0) {
                        gridArray[m  ][n  ][GRID_WATER] = 0;
                    }
                    returnValue = true;
                }
                if (gridArray[m  ][n  ][GRID_WATER] + gridArray[m  ][n  ][GRID_HEIGHT] >
                    gridArray[m+1][n  ][GRID_WATER] + gridArray[m+1][n  ][GRID_HEIGHT]) { // 下
                    gridArray[m  ][n  ][GRID_WATER] =
                    gridArray[m+1][n  ][GRID_WATER] + gridArray[m+1][n  ][GRID_HEIGHT]
                                                    - gridArray[m  ][n  ][GRID_HEIGHT];
                    if (gridArray[m  ][n  ][GRID_WATER] < 0) {
                        gridArray[m  ][n  ][GRID_WATER] = 0;
                    }
                    returnValue = true;
                }
                if (gridArray[m  ][n  ][GRID_WATER] + gridArray[m  ][n  ][GRID_HEIGHT] >
                    gridArray[m  ][n-1][GRID_WATER] + gridArray[m  ][n-1][GRID_HEIGHT]) { // 左
                    gridArray[m  ][n  ][GRID_WATER] =
                    gridArray[m  ][n-1][GRID_WATER] + gridArray[m  ][n-1][GRID_HEIGHT]
                                                    - gridArray[m  ][n  ][GRID_HEIGHT];
                    if (gridArray[m  ][n  ][GRID_WATER] < 0) {
                        gridArray[m  ][n  ][GRID_WATER] = 0;
                    }
                    returnValue = true;
                }
                if (gridArray[m  ][n  ][GRID_WATER] + gridArray[m  ][n  ][GRID_HEIGHT] >
                    gridArray[m  ][n+1][GRID_WATER] + gridArray[m  ][n+1][GRID_HEIGHT]) { // 右
                    gridArray[m  ][n  ][GRID_WATER] =
                    gridArray[m  ][n+1][GRID_WATER] + gridArray[m  ][n+1][GRID_HEIGHT]
                                                    - gridArray[m  ][n  ][GRID_HEIGHT];
                    if (gridArray[m  ][n  ][GRID_WATER] < 0) {
                        gridArray[m  ][n  ][GRID_WATER] = 0;
                    }
                    returnValue = true;
                }
            }
        }        return returnValue;
    }    private static void postprocess() { // 后处理
        int totalWater = 0; // 合计储存水量
        for (int m = 0; m < M; m++) {
            for (int n = 0; n < N; n++) {
                totalWater += gridArray[m][n][GRID_WATER];
            }
        }
        System.out.println("合计储存水量" + "：" + totalWater);
    }    private static void printArray(final int gridIndex) { // 打印数组
        switch (gridIndex) {
        case GRID_HEIGHT:
            System.out.println("方格高度" + "：");
            break;
        case GRID_WATER:
            System.out.println("储存水量" + "：");
            break;
        default:
            break;
        }
        for (int m = 0; m < M; m++) {
            for (int n = 0; n < N; n++) {
                System.out.print(gridArray[m][n][gridIndex] + " ");
            }
            System.out.println();
        }
    }
}