How to solve a problem about the accumulation of water in the landscape?

Question

Given an array of numbers:

1 2 3 4 6 3 2 4 7 3 4 6 1 2 1

Each number in this array indicates height. The combination of heights forms a two-dimensional landscape.

Imagine that it is raining and water accumulates in the pits of this landscape. It is necessary to calculate how many cells the water fills.

The ideal solution to this problem involves passing through the array once.

Implement on js with the input of an array of numbers and schematic visualization of the landscape, as well as the output of the result.

Graphic output made via chart.js http://prntscr.com/mthgtk

Here is a solution

HTML

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta http-equiv="X-UA-Compatible" content="ie=edge"> <title>Document</title> <script src="./data.js"></script> </head> <style> #app { display: flex; padding-top: 100px; padding-left: 200px; } .cube { height: 50px; width: 50px; background-color: gray; margin:1px; display: flex; align-items: center; justify-content: center; font-size: 20px; font-weight: bold; color: brown; } .column { display: flex; flex-direction: column-reverse; } .water { height: 50px; width: 50px; background-color: rgb(26, 123, 187); margin:1px; display: flex; align-items: center; justify-content: center; font-size: 20px; font-weight: bold; color: brown; } </style> <body> <div id="app"> </div> </body> </html>

Js

 window.onload = () => { const app = document.getElementById('app'); const coors = [1, 2, 3, 4, 6, 3, 2, 4, 7, 3, 4, 6, 1, 2, 1]; const highest = coors.map(v => v).sort().reverse()[0]; for (const el of coors) { let col = createColumn(); for (let i = 0; i < el; i++) { const cube = createCube(); cube.innerHTML = i + 1; col.appendChild(cube); } for (let j = 0; j < highest - el; j++) { const cube = createWater(); cube.innerHTML = j + 1; col.appendChild(cube); } app.appendChild(col); } var colums = Array.from(app.getElementsByClassName('column')); var copy = Object.assign({}, colums); for (let index = 0; index < colums.length; index++) { if (colums[index - 1]) { const groundLeft = colums[index - 1].getElementsByClassName('cube').length; const groundCenter = colums[index].getElementsByClassName('cube').length; if ((groundLeft > groundCenter)) { Array .from(colums[index].getElementsByClassName('water')) .forEach(v => colums[index].removeChild(v)); } if ((groundLeft < groundCenter)) { Array .from(colums[index - 1].getElementsByClassName('water')) .forEach(v => colums[index - 1].removeChild(v)); } } } let picks = colums.map((v, i, a) => { const ind = Array.from(v.children).findIndex(z => z.classList.contains('water')); if ( ind> -1) { return { index: i, height: v.getElementsByClassName('cube').length }; } }); const picksAll = picks.filter(v => v).map((v, i, array) => { return { first: array[i], next: array[i + 1] } }).filter(v => v.first && v.next); for (const pick of picksAll) { const height = pick.first.height > pick.next.height ? pick.next.height : pick.first.height; const start = pick.first.index + 1; for (let i = start; i < pick.next.index; i++) { const need = height - copy[i].children.length; for (let j = 0; j < need; j++) { copy[i].appendChild(createWater()); } } Array.from(copy[pick.first.index].children).forEach((v, i, a) => { if (v.classList.contains('water')) { copy[pick.first.index].removeChild(v); } }); Array.from(copy[pick.next.index].children).forEach((v, i, a) => { if (v.classList.contains('water')) { copy[pick.next.index].removeChild(v); } }); } } function createColumn() { const column = document.createElement('div'); column.className = 'column'; return column; } function createCube() { const column = document.createElement('div'); column.className = 'cube'; return column; } function createWater() { const column = document.createElement('div'); column.className = 'water'; return column; }

Comments are not intended for extended discussion; conversation moved to chat . - Yuriy SPb ♦

pavel pavel 8,454 3 22 39 · Answer 1 · 2019-03-05T08:28:58

Solution in C ++ (but in general it is not important, the code +/- is the same). As a demonstration, I only output an answer (it is clear what to fill out). Running example https://ideone.com/M9QHpf

 int v[] = {1, 2, 3, 4, 6, 3, 2, 4, 7, 3, 4, 6, 1, 2, 1}; int count = 0; for (int l=0,r=sizeof(v)/sizeof(v[0]),lM = v[0], rM = v[sizeof(v)/sizeof(v[0])]; l < r; lM = max(lM,v[l]), rM = max(rM,v[r])) if(lM >= rM) count += rM - v[r--]; else count += lM - v[l++]; cout << count<<endl;

Now what's the magic? If we raise the water level, it means that the maximum on the left and the maximum on the right is greater than our current value. (maximum can not be less than the current). Actually to the minimum of the maximum we can add. But there is one thing, we do it in 1 pass and not in 2, so you need to carefully hold 2 pointers to the highs and move the smaller

laid out the problem like this prntscr.com/mtf30h , the difficulty arises only with the understanding of how to calculate the "water".
@mobius, replace int At var, and sizeof(v)/sizeof(v[0]) with length

Answer 2 · 2019-03-05T12:43:56

I give an example implementation on JS with comments:

 let array = prompt('Введите цифры через пробел:', '1 2 3 4 6 3 2 4 7 3 4 6 1 2 1').replace(/ +/g, ' ').trim().split(' '); // вводим массив const height = Math.max(...array); // минимальная высота сетки const width = array.length; // минимальная ширина сетки const air = '–'; // символ воздуха const land = '='; // символ земли const water = '≈'; // символ воды const regExp = `(?${land}(${land}${air}+${land}))`; // регулярное выражение, при котором вода упирается в землю по бокам const grid = []; // инициализируем сетку for (let i = height - 1; i >= 0; i--) { // пробегаем по рядам grid[i] = []; // инициализируем ряд for (let j = 0; j < width; j++) grid[i][j] = (array[j] > 0) ? land : air; // пробегаем по колонкам let string = grid[i].join(''); // преобразовываем массив в строку без запятых let samples = []; // инициализируем вхождения string.replace(new RegExp(regExp, 'g'), (m, g) => samples.push(g)); // собираем совпадения в общий массив (совпадения могут накладываться друг на друга в строке) if (samples.length > 0) { // если совпадения по регулярному выражению найдены, то... samples.forEach((el) => { // для каждого совпадения... string = string.replace(el, el.replace(new RegExp(air, 'g'), water)); // меняем воду на воздух grid[i] = Array.from(string); // сохраняем строку в виде массива }); } array = array.map((el) => (el > 0) ? --el : 0); // с каждым рядом уменьшаем на 1 каждое значение в исходном массиве (но не ниже 0) } for (const el of grid) document.body.innerHTML += `<p>${el.join('').replace(new RegExp(land, 'g'), '<span class="land"> </span>').replace(new RegExp(air, 'g'), '<span class="air"> </span>').replace(new RegExp(water, 'g'), '<span class="water"> </span>')}</p>`; // отрисовываем

 p { font-family: monospace; /* делаем символы в шрифте одинакового размера */ margin: 0; /* убираем отступы */ white-space: pre; /* позволяем пробелам отображаться */ } .air { background-color: lightblue; /* цвет воздуха */ } .land { background-color: green; /* цвет земли */ } .water { background-color: blue; /* цвет воды */ }

PS Minecraft is still far away ... :)

How to solve a problem about the accumulation of water in the landscape?

2 answers 2

More articles: