Водоемкость 2D массива
Я должен сделать небольшое упражнение в моем университете, но я уже застрял на некоторое время. Упражнение состоит в том, чтобы рассчитать водную емкость 2D-массива, пользователь должен ввести ширину (w) и высоту (h) 2D-массива, а затем все элементы массива, которые представляют высоту в этом месте., Действительно простой пример:
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. Тем не менее, я протестировал много решений, и некоторые из них действительно прошли через мои первые четыре контрольных примера, однако большинство из них уже не справились с простыми. Talent buddy плохо выполнил контрольные тесты: на самом деле их всего два. Если вы хотите увидеть решения, которые у них есть, просто зарегистрируйтесь и введите этот код (язык 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 - это рабочее решение, однако, как и мое решение, оно недостаточно эффективно, чтобы выдерживать более крупные входные тесты, у кого-нибудь есть идея для более эффективной реализации?
Любые идеи и помощь будут высоко ценится.
2 ответа
Вот мой взгляд на проблему. Идея заключается в следующем: вы многократно заполняете массив, используя увеличение "уровня моря". Уровень, на котором узел сначала залил, будет того же уровня, на котором вода останется в этом узле при отступлении "наводнения".
- для каждой высоты, начиная с самого низкого до самого высокого уровня:
- положить внешние узлы в набор, называемый бахромой
- в то время как есть больше узлов в наборе краев, вытолкнуть узел из набора
- если этот узел был впервые достигнут в этой итерации и его высота меньше или равна текущей высоте наводнения, запомните текущую высоту наводнения для этого узла
- добавить все соседние области, которые еще не были затоплены и имеют высоту, меньшую или равную текущей высоте затопления, к краю
В его нынешнем виде это будет иметь значение O(nmz) для массива n x m с максимальным углом места z, но с некоторой оптимизацией мы можем уменьшить его до O (нм). Для этого вместо использования только одной полосы, и каждый раз, когда мы прокладываем путь снаружи снаружи, мы используем несколько наборов полос, по одному для каждого уровня высоты, и помещаем узлы, которых мы достигаем, в полосу, соответствующие их собственным высота (или текущая полоса, если они ниже). Таким образом, каждый узел в массиве добавляется и удаляется из края ровно один раз. И это так быстро, как только возможно.
Вот код Я сделал это на 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()
Файл должен содержать только необработанный массив, как в вашем вопросе, без информации об измерениях, разделенный пробелами и переносами строк.
talentbuddy.co имеет эту проблему как одну из своих задач кодирования. Это называется дождь, если вы создадите учетную запись, вы можете просматривать решения других людей.
#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;
}