二维数组的水容量
Water capacity of a 2D array
我必须在我的大学做一些运动，但我已经困了一段时间了。练习是关于计算二维数组的水容量，用户必须输入二维数组的宽度（w）和高度（h），然后是数组的所有元素，代表该位置的高度.非常简单的例子：
10 10 10
10 2 10
10 10 10
然后输出将是 8，因为这是适合其中的最大水量。另一个例子是：
6 4
1 5 1 5 4 3
5 1 5 1 2 4
1 5 1 4 1 5
3 1 3 6 4 1
输出将为 14。
另外需要注意的是：数组的宽度和高度不能大于1000，元素的高度不能大于10^5。
现在我基本上有了解决方案，但是对于更大的输入来说它不够快。我所做的如下：我将高度添加到 TreeSet，然后每次我轮询最后一个（最高）然后我遍历数组（不看边缘）并使用 DFS 并检查每个位置是否水可以留在里面。如果水没有超出阵列，则计算水下的位置，如果超出阵列，则再次轮询并执行相同操作。
我还尝试通过垂直和水平方向查看阵列中的峰值。对于上面的例子，你得到这个：
0 5 0 5 4 0
5 0 5 0 0 4
0 5 0 4 0 5
3 1 3 6 4 0
我用这个做的是给峰一个颜色，比如说（黑色），然后对于所有的白色再次用 DFS 取最小峰值，然后取最小值来计算水容量。但这不起作用，因为例如：
7 7 7 7 7
7 4 4 4 7
7 2 3 1 7
7 4 4 4 7
7 7 7 7 7
现在3是高峰，但是到处都是7水位。所以这行不通。
但是因为我的解决方案不够快，所以我正在寻找更高效的解决方案。这是神奇发生的代码部分：
while (p.size() != 0 || numberOfNodesVisited!= (w-2)*(h-2)) {
max = p.pollLast();
for (int i=1; i < h-1; i++) {
for (int j=1; j < w-1; j++) {
if (color[i][j] == 0) {
DFSVisit(profile, i, j);
if (!waterIsOut) {
sum+= solveSubProblem(heights, max);
numberOfNodesVisited += heights.size();
for(int x = 0; x < color.length; x++) {
color2[x] = color[x].clone();
}
} else {
for(int x = 0; x < color2.length; x++) {
color[x] = color2[x].clone();
}
waterIsOut = false;
}
heights.clear();
}
}
}
}
注意我每次都重新设置路径和颜色，我认为这是必须改进的部分。
我的 DFS：我有三种颜色 2（黑色）它被访问，1（灰色）如果它是边缘，0（白色）如果没有被访问而不是边缘。
public void DFSVisit(int[][] profile, int i, int j) {
color[i][j] = 2; // black
heights.add(profile[i][j]);
if (!waterIsOut && heights.size() < 500) {
if (color[i+1][j] == 0 && max > profile[i+1][j]) { // up
DFSVisit(profile, i+1, j);
} else if (color[i+1][j] == 1 && max > profile[i+1][j]) {
waterIsOut = true;
}
if (color[i-1][j] == 0 && max > profile[i-1][j]) { // down
DFSVisit(profile, i-1, j);
} else if (color[i-1][j] == 1 && max > profile[i-1][j]) {
waterIsOut = true;
}
if (color[i][j+1] == 0 && max > profile[i][j+1]) { // right
DFSVisit(profile, i, j+1);
} else if (color[i][j+1] == 1 && max > profile[i][j+1]) {
waterIsOut = true;
}
if (color[i][j-1] == 0 && max > profile[i][j-1]) { //left
DFSVisit(profile, i, j-1);
} else if (color[i][j-1] == 1 && max > profile[i][j-1]) {
waterIsOut = true;
}
}
}
更新
@dufresnb 提到了 talentbuddy.co，其中在 https://www.talentbuddy.co/challenge/526efd7f4af0110af3836603 给出了相同的练习。然而，我测试了很多解决方案，其中一些实际上通过了我的前四个测试用例，但是大多数已经在简单的测试上失败了。人才伙伴在制作测试用例方面做得很糟糕：实际上他们只有两个。如果你想看他们刚刚注册并输入代码（C语言）的解决方案：通过他们的测试用例就足够了
#include <stdio.h>
void rain(int m, int *heights, int heights_length) {
//What tests do we have here?
if (m==6)
printf("5");
else if (m==3)
printf("4");
//Looks like we need some more tests.
}
更新
@tobias_k 解决方案是一个有效的解决方案，但是就像我的解决方案一样，它的效率不足以通过更大的输入测试用例，有没有人有更有效的实施的想法？
任何想法和帮助将不胜感激。
talentbuddy.co 将这个问题作为他们的编码任务之一。就叫rain，注册一个账号就可以查看别人的解法
#include <iostream>
#include <vector>
bool check(int* myHeights, int x, int m, bool* checked,int size)
{
checked[x]=true;
if(myHeights[x-1]==myHeights[x] && (x-1)%m!=0 && !checked[x-1])
{
if(!check(myHeights,x-1,m,checked,size))return false;
}
else if((x-1)%m==0 && myHeights[x-1]<=myHeights[x])
{
return false;
}
if(myHeights[x+1]==myHeights[x] && (x+1)%m!=m-1 && !checked[x+1])
{
if(!check(myHeights,x+1,m,checked,size))return false;
}
else if((x+1)%m==m-1 && myHeights[x+1]<=myHeights[x])
{
return false;
}
if(myHeights[x-m]==myHeights[x] && (x-m)>m && !checked[x-m])
{
if(!check(myHeights,x-m,m,checked,size))return false;
}
else if((x-m)<m && myHeights[x-m]<=myHeights[x])
{
return false;
}
if(myHeights[x+m]==myHeights[x] && (x+m)<size-m && !checked[x+m])
{
if(!check(myHeights,x+m,m,checked,size))return false;
}
else if((x+m)>size-m && myHeights[x+m]<=myHeights[x])
{
return false;
}
return true;
}
void rain(int m, const std::vector<int> &heights)
{
int total=0;
int max=1;
if(m<=2 || heights.size()/m<=2)
{
std::cout << total << std::endl;
return;
}
else
{
int myHeights[heights.size()];
for(int x=0;x<heights.size();++x)
{
myHeights[x]=heights[x];
}
bool done=false;
while(!done)
{
done=true;
for(int x=m+1;x<heights.size()-m;++x)
{
if(x<=m || x%m==0 || x%m==m-1)
{
continue;
}
int lower=0;
if(myHeights[x]<myHeights[x-1])++lower;
if(myHeights[x]<myHeights[x+1])++lower;
if(myHeights[x]<myHeights[x-m])++lower;
if(myHeights[x]<myHeights[x+m])++lower;
if(lower==4)
{
++total;
++myHeights[x];
done=false;
}
else if(lower>=2)
{
bool checked[heights.size()];
for(int y=0;y<heights.size();++y)
{
checked[y]=false;
}
if(check(myHeights,x,m,checked,heights.size()))
{
++total;
++myHeights[x];
done=false;
}
}
}
}
}
std::cout << total << std::endl;
return;
}
这是我对这个问题的看法。思路如下：你重复flood-fill数组使用递增"sea levels"。当 "flood" 撤退时，节点首先被淹没的水位将与水在该节点上方汇集的水位相同。
- 对于从最低到最高级别的每个高度：
- 将外部节点放入一个集合中，称为边缘
- 当边缘集中有更多节点时，从集合中弹出一个节点
- 如果在本次迭代中首先到达该节点并且其高度小于或等于当前洪水高度，则记住该节点的当前洪水高度
- 将所有尚未被淹没且高度小于或等于当前洪水高度的邻居添加到边缘
就目前而言，对于具有最大仰角 z 的 n x m 阵列，这将具有复杂性 O(nmz) ，但通过一些优化，我们可以将其降低到 O(nm)。为此，我们不是只使用一个边缘，每次都从外向内工作，而是使用多个边缘集，每个高度级别一个，并将我们到达的节点放在与其自身相对应的边缘中高度（或当前边缘，如果它们较低）。这样，数组中的每个节点都被添加到边缘和从边缘删除恰好一次。这已经是最快的速度了。
这是一些代码。我已经在 Python 中完成了它，但您应该能够将它转移到 Java —— 假装它是可执行的伪代码。您可以添加一个计数器来查看 while 循环体确实执行了 24 次，对于本示例，结果为 14.
# setup and preparations
a = """1 5 1 5 4 3
5 1 5 1 2 4
1 5 1 4 1 5
3 1 3 6 4 1"""
array = [[int(x) for x in line.strip().split()]
for line in a.strip().splitlines()]
cols, rows = len(array[0]), len(array)
border = set([(i, 0 ) for i in range(rows)] +
[(i, cols-1) for i in range(rows)] +
[(0, i ) for i in range(cols)] +
[(rows-1, i) for i in range(cols)])
lowest = min(array[x][y] for (x, y) in border) # lowest on border
highest = max(map(max, array)) # highest overall
# distribute fringe nodes to separate fringes, one for each height level
import collections
fringes = collections.defaultdict(set) # maps points to sets
for (x, y) in border:
fringes[array[x][y]].add((x, y))
# 2d-array how high the water can stand above each cell
fill_height = [[None for _ in range(cols)] for _ in range(rows)]
# for each consecutive height, flood-fill from current fringe inwards
for height in range(lowest, highest + 1):
while fringes[height]: # while this set is non-empty...
# remove next cell from current fringe and set fill-height
(x, y) = fringes[height].pop()
fill_height[x][y] = height
# put not-yet-flooded neighbors into fringe for their elevation
for x2, y2 in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]:
if 0 <= x2 < rows and 0 <= y2 < cols and fill_height[x2][y2] is None:
# get fringe for that height, auto-initialize with new set if not present
fringes[max(height, array[x2][y2])].add((x2, y2))
# sum of water level minus ground level for all the cells
volume = sum(fill_height[x][y] - array[x][y] for x in range(cols) for y in range(rows))
print "VOLUME", volume
要从文件中读取更大的测试用例，请将顶部的 a = """...""" 替换为：
with open("test") as f:
a = f.read()
文件应该只包含问题中的原始数组，没有维度信息，用空格和换行符分隔。
我必须在我的大学做一些运动，但我已经困了一段时间了。练习是关于计算二维数组的水容量，用户必须输入二维数组的宽度（w）和高度（h），然后是数组的所有元素，代表该位置的高度.非常简单的例子：
10 10 10
10 2 10
10 10 10
然后输出将是 8，因为这是适合其中的最大水量。另一个例子是：
6 4
1 5 1 5 4 3
5 1 5 1 2 4
1 5 1 4 1 5
3 1 3 6 4 1
输出将为 14。
另外需要注意的是：数组的宽度和高度不能大于1000，元素的高度不能大于10^5。
现在我基本上有了解决方案，但是对于更大的输入来说它不够快。我所做的如下：我将高度添加到 TreeSet，然后每次我轮询最后一个（最高）然后我遍历数组（不看边缘）并使用 DFS 并检查每个位置是否水可以留在里面。如果水没有超出阵列，则计算水下的位置，如果超出阵列，则再次轮询并执行相同操作。
我还尝试通过垂直和水平方向查看阵列中的峰值。对于上面的例子，你得到这个：
0 5 0 5 4 0
5 0 5 0 0 4
0 5 0 4 0 5
3 1 3 6 4 0
我用这个做的是给峰一个颜色，比如说（黑色），然后对于所有的白色再次用 DFS 取最小峰值，然后取最小值来计算水容量。但这不起作用，因为例如：
7 7 7 7 7
7 4 4 4 7
7 2 3 1 7
7 4 4 4 7
7 7 7 7 7
现在3是高峰，但是到处都是7水位。所以这行不通。
但是因为我的解决方案不够快，所以我正在寻找更高效的解决方案。这是神奇发生的代码部分：
while (p.size() != 0 || numberOfNodesVisited!= (w-2)*(h-2)) {
max = p.pollLast();
for (int i=1; i < h-1; i++) {
for (int j=1; j < w-1; j++) {
if (color[i][j] == 0) {
DFSVisit(profile, i, j);
if (!waterIsOut) {
sum+= solveSubProblem(heights, max);
numberOfNodesVisited += heights.size();
for(int x = 0; x < color.length; x++) {
color2[x] = color[x].clone();
}
} else {
for(int x = 0; x < color2.length; x++) {
color[x] = color2[x].clone();
}
waterIsOut = false;
}
heights.clear();
}
}
}
}
注意我每次都重新设置路径和颜色，我认为这是必须改进的部分。
我的 DFS：我有三种颜色 2（黑色）它被访问，1（灰色）如果它是边缘，0（白色）如果没有被访问而不是边缘。
public void DFSVisit(int[][] profile, int i, int j) {
color[i][j] = 2; // black
heights.add(profile[i][j]);
if (!waterIsOut && heights.size() < 500) {
if (color[i+1][j] == 0 && max > profile[i+1][j]) { // up
DFSVisit(profile, i+1, j);
} else if (color[i+1][j] == 1 && max > profile[i+1][j]) {
waterIsOut = true;
}
if (color[i-1][j] == 0 && max > profile[i-1][j]) { // down
DFSVisit(profile, i-1, j);
} else if (color[i-1][j] == 1 && max > profile[i-1][j]) {
waterIsOut = true;
}
if (color[i][j+1] == 0 && max > profile[i][j+1]) { // right
DFSVisit(profile, i, j+1);
} else if (color[i][j+1] == 1 && max > profile[i][j+1]) {
waterIsOut = true;
}
if (color[i][j-1] == 0 && max > profile[i][j-1]) { //left
DFSVisit(profile, i, j-1);
} else if (color[i][j-1] == 1 && max > profile[i][j-1]) {
waterIsOut = true;
}
}
}
更新 @dufresnb 提到了 talentbuddy.co，其中在 https://www.talentbuddy.co/challenge/526efd7f4af0110af3836603 给出了相同的练习。然而，我测试了很多解决方案，其中一些实际上通过了我的前四个测试用例，但是大多数已经在简单的测试上失败了。人才伙伴在制作测试用例方面做得很糟糕：实际上他们只有两个。如果你想看他们刚刚注册并输入代码（C语言）的解决方案：通过他们的测试用例就足够了
#include <stdio.h>
void rain(int m, int *heights, int heights_length) {
//What tests do we have here?
if (m==6)
printf("5");
else if (m==3)
printf("4");
//Looks like we need some more tests.
}
更新 @tobias_k 解决方案是一个有效的解决方案，但是就像我的解决方案一样，它的效率不足以通过更大的输入测试用例，有没有人有更有效的实施的想法？
任何想法和帮助将不胜感激。
talentbuddy.co 将这个问题作为他们的编码任务之一。就叫rain，注册一个账号就可以查看别人的解法
#include <iostream>
#include <vector>
bool check(int* myHeights, int x, int m, bool* checked,int size)
{
checked[x]=true;
if(myHeights[x-1]==myHeights[x] && (x-1)%m!=0 && !checked[x-1])
{
if(!check(myHeights,x-1,m,checked,size))return false;
}
else if((x-1)%m==0 && myHeights[x-1]<=myHeights[x])
{
return false;
}
if(myHeights[x+1]==myHeights[x] && (x+1)%m!=m-1 && !checked[x+1])
{
if(!check(myHeights,x+1,m,checked,size))return false;
}
else if((x+1)%m==m-1 && myHeights[x+1]<=myHeights[x])
{
return false;
}
if(myHeights[x-m]==myHeights[x] && (x-m)>m && !checked[x-m])
{
if(!check(myHeights,x-m,m,checked,size))return false;
}
else if((x-m)<m && myHeights[x-m]<=myHeights[x])
{
return false;
}
if(myHeights[x+m]==myHeights[x] && (x+m)<size-m && !checked[x+m])
{
if(!check(myHeights,x+m,m,checked,size))return false;
}
else if((x+m)>size-m && myHeights[x+m]<=myHeights[x])
{
return false;
}
return true;
}
void rain(int m, const std::vector<int> &heights)
{
int total=0;
int max=1;
if(m<=2 || heights.size()/m<=2)
{
std::cout << total << std::endl;
return;
}
else
{
int myHeights[heights.size()];
for(int x=0;x<heights.size();++x)
{
myHeights[x]=heights[x];
}
bool done=false;
while(!done)
{
done=true;
for(int x=m+1;x<heights.size()-m;++x)
{
if(x<=m || x%m==0 || x%m==m-1)
{
continue;
}
int lower=0;
if(myHeights[x]<myHeights[x-1])++lower;
if(myHeights[x]<myHeights[x+1])++lower;
if(myHeights[x]<myHeights[x-m])++lower;
if(myHeights[x]<myHeights[x+m])++lower;
if(lower==4)
{
++total;
++myHeights[x];
done=false;
}
else if(lower>=2)
{
bool checked[heights.size()];
for(int y=0;y<heights.size();++y)
{
checked[y]=false;
}
if(check(myHeights,x,m,checked,heights.size()))
{
++total;
++myHeights[x];
done=false;
}
}
}
}
}
std::cout << total << std::endl;
return;
}
这是我对这个问题的看法。思路如下：你重复flood-fill数组使用递增"sea levels"。当 "flood" 撤退时，节点首先被淹没的水位将与水在该节点上方汇集的水位相同。
- 对于从最低到最高级别的每个高度：
- 将外部节点放入一个集合中，称为边缘
- 当边缘集中有更多节点时，从集合中弹出一个节点
- 如果在本次迭代中首先到达该节点并且其高度小于或等于当前洪水高度，则记住该节点的当前洪水高度
- 将所有尚未被淹没且高度小于或等于当前洪水高度的邻居添加到边缘
就目前而言，对于具有最大仰角 z 的 n x m 阵列，这将具有复杂性 O(nmz) ，但通过一些优化，我们可以将其降低到 O(nm)。为此，我们不是只使用一个边缘，每次都从外向内工作，而是使用多个边缘集，每个高度级别一个，并将我们到达的节点放在与其自身相对应的边缘中高度（或当前边缘，如果它们较低）。这样，数组中的每个节点都被添加到边缘和从边缘删除恰好一次。这已经是最快的速度了。
这是一些代码。我已经在 Python 中完成了它，但您应该能够将它转移到 Java —— 假装它是可执行的伪代码。您可以添加一个计数器来查看 while 循环体确实执行了 24 次，对于本示例，结果为 14.
# setup and preparations
a = """1 5 1 5 4 3
5 1 5 1 2 4
1 5 1 4 1 5
3 1 3 6 4 1"""
array = [[int(x) for x in line.strip().split()]
for line in a.strip().splitlines()]
cols, rows = len(array[0]), len(array)
border = set([(i, 0 ) for i in range(rows)] +
[(i, cols-1) for i in range(rows)] +
[(0, i ) for i in range(cols)] +
[(rows-1, i) for i in range(cols)])
lowest = min(array[x][y] for (x, y) in border) # lowest on border
highest = max(map(max, array)) # highest overall
# distribute fringe nodes to separate fringes, one for each height level
import collections
fringes = collections.defaultdict(set) # maps points to sets
for (x, y) in border:
fringes[array[x][y]].add((x, y))
# 2d-array how high the water can stand above each cell
fill_height = [[None for _ in range(cols)] for _ in range(rows)]
# for each consecutive height, flood-fill from current fringe inwards
for height in range(lowest, highest + 1):
while fringes[height]: # while this set is non-empty...
# remove next cell from current fringe and set fill-height
(x, y) = fringes[height].pop()
fill_height[x][y] = height
# put not-yet-flooded neighbors into fringe for their elevation
for x2, y2 in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]:
if 0 <= x2 < rows and 0 <= y2 < cols and fill_height[x2][y2] is None:
# get fringe for that height, auto-initialize with new set if not present
fringes[max(height, array[x2][y2])].add((x2, y2))
# sum of water level minus ground level for all the cells
volume = sum(fill_height[x][y] - array[x][y] for x in range(cols) for y in range(rows))
print "VOLUME", volume
要从文件中读取更大的测试用例，请将顶部的 a = """...""" 替换为：
with open("test") as f:
a = f.read()
文件应该只包含问题中的原始数组，没有维度信息，用空格和换行符分隔。