Last active
February 17, 2022 07:58
-
-
Save sagittaracc/17cd90dfedf147e527d946ec2ff093aa to your computer and use it in GitHub Desktop.
River Sizes | AlgoExpert
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Проверяет выход за границы матрицы при её обходе по рекам | |
* @param array matrix исходная матрица | |
* @param int line позиция по горизонтали в матрице | |
* @param int column позиция по вертикали в матрице | |
* @return boolean | |
*/ | |
function isOffMatrix(matrix, line, column) { | |
return line < 0 | |
|| column < 0 | |
|| line > matrix.length - 1 | |
|| column > matrix[line].length - 1; | |
} | |
/** | |
* Проверяет является ли запрошенная позиция частью реки | |
* @param array matrix исходная матрица | |
* @param int line позиция по горизонтали в матрице | |
* @param int column позиция по вертикали в матрице | |
* @return boolean | |
*/ | |
function isPartOfRiver(matrix, line, column) { | |
return isOffMatrix(matrix, line, column) | |
? false | |
: matrix[line][column] === 1; | |
} | |
/** | |
* Помечает запрошенную позицию как ранее пройденную | |
* @param array matrix исходная матрица | |
* @param int line позиция по горизонтали в матрице | |
* @param int column позиция по вертикали в матрице | |
*/ | |
function visite(matrix, line, column) { | |
if (line !== null && column !== null) { | |
matrix[line][column] = -1; | |
} | |
} | |
/** | |
* Помечает заданную позицию в матрице текущим значением шага | |
* @param array matrix исходная матрица | |
* @param int line позиция по горизонтали в матрице | |
* @param int column позиция по вертикали в матрице | |
*/ | |
function setStep(matrix, line, column, stepIndex) { | |
matrix[line][column] = stepIndex; | |
} | |
/** | |
* Рекурсивный шаг в очередную позицию в матрице | |
* @param array matrix исходная матрица | |
* @param int currentLine текущая позиция по горизонтали в матрице | |
* @param int currentColumn текущая позиция по вертикали в матрице | |
* @param int prevLine позиция по горизонтали в матрице откуда пришли | |
* @param int prevColumn позиция по вертикали в матрице откуда пришли | |
* @param int stepIndex текущее значение шага при обходе | |
* @return int текущее значение шага после обхода во все возможные стороны | |
*/ | |
function stepInto(matrix, currentLine, currentColumn, prevLine, prevColumn, stepIndex) { | |
setStep(matrix, currentLine, currentColumn, stepIndex); | |
visite(matrix, prevLine, prevColumn); | |
if (isPartOfRiver(matrix, currentLine, currentColumn - 1)) { | |
stepIndex = stepInto(matrix, currentLine, currentColumn - 1, currentLine, currentColumn, stepIndex + 1); | |
} | |
if (isPartOfRiver(matrix, currentLine, currentColumn + 1)) { | |
stepIndex = stepInto(matrix, currentLine, currentColumn + 1, currentLine, currentColumn, stepIndex + 1); | |
} | |
if (isPartOfRiver(matrix, currentLine - 1, currentColumn)) { | |
stepIndex = stepInto(matrix, currentLine - 1, currentColumn, currentLine, currentColumn, stepIndex + 1); | |
} | |
if (isPartOfRiver(matrix, currentLine + 1, currentColumn)) { | |
stepIndex = stepInto(matrix, currentLine + 1, currentColumn, currentLine, currentColumn, stepIndex + 1); | |
} | |
return stepIndex; | |
} | |
/** | |
* Main | |
*/ | |
function riverSizes(matrix) { | |
var sizes = []; | |
matrix.map(function (row, line) { | |
row.map(function (cell, column) { | |
if (isPartOfRiver(matrix, line, column)) { | |
if ((size = stepInto(matrix, line, column, null, null, 1)) > 0) { | |
sizes.push(size); | |
} | |
} | |
}) | |
}) | |
return sizes; | |
} | |
exports.riverSizes = riverSizes; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment