Standard "sapper". The field is 16 by 16 cells. 20 minutes on the field.

When you first press the player obviously misses the cell with a mine. He gets either on an empty cage or on a cage containing information about the number of mines around. Let's call it a cell with a number.

If a player clicks on a cell with a number, we open it only. If a player has clicked on a completely empty cell, then besides this cell itself, it is required to open all (related, I can’t find the translation. Whether they are connected) cells, including those that contain a number, but not further than them. Something like this:

Field with mines

The player clicked on the green dot. Reds contain mines. Yellow contain numbers. Purple displays those cells that should be opened along with green. (Yes, some of the yellow purple marks are not accidental, they should also be open).

Actually, the algorithm of searching for these very purple cells is of interest .
Also, if there are any implementation subtleties regarding JavaScript, I will also be happy to listen.

  • Variation of the usual flood fill . Since the position of the mines does not change, yellow cells can be marked in advance to facilitate the task. - D-side

2 answers 2

The easiest algorithm:

If the cell is empty, check the adjacent cells: left, right, top, bottom
enter image description here
It is worth paying attention to the boundary case, as in the example in question, when there is no cell to the right and below.

If not empty - do nothing.

Pseudocode

функция Проверить ячейку (ячейка) если ячейка проверерена -> выход если ячейка не пустая -> выход Отметить, что ячейка проверена, чтобы не проверять дважды. Проверить ячейку сверху если есть Проверить ячейку снизу если есть Проверить ячейку слева если есть Проверить ячейку справа если есть конец функции

Option without recursion:

 функция Проверить ячейку (ячейку) если ячейка не пустая -> выход получить ячейки для проверки <- [ ячейка сверху если есть ячейка снизу если есть ячейка слева если есть ячейка справа если есть ] // смежные Пока есть ячейки для проверки: если текущая ячейка пустая и не проверенная, то отметить ячейку как проверенную. удалить ее из списка ячеек для проверки. добавить в список ячеек для проверки смежные не проверенные ячейки конец функции
  • but after all cells with numbers can defend further than one cell. - smellyshovel
  • @smellyshovel, do not worry, they will turn because you will check the neighboring until you get to a non-empty cell. - Grundy
  • Plus, the cells are diagonally, which can also contain numbers and should also be open. Here, it would be worth checking the neighboring 8, but more than one. - smellyshovel
  • I did not understand this at all. Why will I check until I come across an open one? On the contrary, it seems like - smellyshovel
  • @smellyshovel, added pseudocode, I think it should become clearer - Grundy

let's say there are nums (point) - returns 0 on purple and> 0 on the rest. let's say there is dist (pointA, pointB) - (float) returns the distance between the cells. let's say there is closedPoints - this is an array of not yet open cells

 // для волн сбора фиолетовых клеток до кучи function nearestPinc(pointA, openList) { function okDist(pointB) { return dist(pointA, pointB) == 1; } // клетка пустая(фиолетовая) и она близка к pointA if (nums(pointA) == 0 && openList.find(okDist)) { openList.push(pointA); } return openList; } // для последней волны сбора жёлтых клеток function nearestYellow(pointA, openList) { function okDist(pointB) { return dist(pointA, pointB) < 2; } // клетка близка к pointA if (openList.find(okDist)) { openList.push(pointA); } return openList; } function getOpenList(point) { let openList = [point]; if (nums(point) > 0) // ткнули в жёлтую return openList; // собираем все повязанные фиолетовые клеточки let L = openList.length; // пока находим фиолетовые клетки достаточно близкие к уже найденным while (L < (openList = closedPoints.reduce(nearestPinc, openList)).length) { L = openList.length; } return closedPoints.reduce(nearestYellow, openList) }