Проблема с концевыми путями в простом рекурсивном алгоритме

Question

Прежде всего: это не домашнее задание, это для моего хобби-проекта.

Справочная информация: В своей игре-головоломке на Java я использую очень простой рекурсивный алгоритм для проверкиесли определенные места на «карте» стали изолированными после того, как часть помещена.Изолированный в этом случае означает: где никакие части не могут быть размещены.

Текущий алгоритм:

public int isolatedSpace(Tile currentTile, int currentSpace){
        if(currentTile != null){
            if(currentTile.isOpen()){
                currentTile.flag(); // mark as visited
                currentSpace += 1;
                currentSpace = isolatedSpace(currentTile.rightNeighbor(),currentSpace);
                currentSpace = isolatedSpace(currentTile.underNeighbor(),currentSpace);
                currentSpace = isolatedSpace(currentTile.leftNeighbor(),currentSpace);
                currentSpace = isolatedSpace(currentTile.upperNeighbor(),currentSpace);
                if(currentSpace < 3){currentTile.markAsIsolated();} // <-- the problem
            }
        }
        return currentSpace;
    }

Этот фрагмент кода возвращает размер пустого пространства, частью которого является начальная плитка,Эта часть кода работает как задумано.Но я столкнулся с проблемой, касающейся маркировки плиток, и именно поэтому название этого вопроса уместно;)

Проблема: Проблема в том, что некоторые плитки никогда не пересматриваются'(они возвращают значение и завершаются, поэтому никогда не получат возвращаемое значение сами из более позднего воплощения, чтобы обновить размер пустого пространства).Эти «забытые» листы могут быть частью большого пространства, но все же помечены как изолированные, потому что они были посещены в начале процесса, когда currentSpace имел низкое значение.

Вопрос: Как улучшить этот код, чтобы он устанавливал правильное значение для плиток без особых накладных расходов?Я могу подумать об уродливых решениях, таких как пересмотр всех помеченных плиток и проверка правильности их значения, если соседи имеют одинаковое значение, если не обновление и т. Д. Но я уверен, что на переполнении стека есть замечательные люди с гораздо лучшими идеями;)

---

Обновление: Я внес некоторые изменения.

public int isolatedSpace(Tile currentTile, int currentSpace, LinkedList<Tile> visitedTiles){
        if(currentTile != null){
            if(currentTile.isOpen()){
                // do the same as before
                visitedTiles.add(); 
            }
        }
        return currentSpace;
    }

И функция marktiles (вызывается, только когда возвращаемый размер пространства меньше заданногозначение)

marktiles(visitedTiles){
       for(Tile t : visitedTiles){
            t.markAsIsolated();
       }
}

Этот подход согласуется с ответом Рекса Керра, по крайней мере, если я понял его идею.

Answer 1

Это не общее решение, но вы помечаете пробелы как изолированные, если они встречаются в области из двух или менее пробелов. Разве вы не можете упростить этот тест до «пространства изолированно, если (а) у него нет открытых соседей или (б) точно один открытый сосед и у этого соседа нет других открытых соседей».

Answer 2

Вам необходимо выполнить двухэтапный процесс: собрать информацию о том, является ли пространство изолированным, а затем пометить как изолированное. Поэтому вам нужно сначала подсчитать все пробелы (используя одну рекурсивную функцию), а затем отметить все связанные пробелы, если критерий пройдет (используя другую рекурсивную функцию).