Проверка всех выбранных фрагментов на 2d-матрице

Question

Я создаю игру с картой, которая является [100 плитки х 100 плитки] матрицы. Игроки смогут создавать «герцогства», объединяя 4 плитки. Игра позволит игроку выбрать 4 плитки и проверить, все ли эти плитки связаны друг с другом и позволяют игроку создать герцогство только в том случае, если это так.

Так что мой isConnected() метод будет принимать в ArrayList<Tiles> и плитки имеют getX() и getY() методы, которые возвращает их X и Y координаты на сетке. Если плитки связаны друг с другом, они вернут true или false, если они не являются. Обратите внимание, что плитки не могут быть установлены по диагонали.

Следует отметить, что этот метод должен работать для плиток ArrayList с более чем 4-мя плитами, так как ему нужно будет проверять более крупные списки плиток и что сценарий Герцогства является примером того, как этот метод будет использоваться.

---

Просто для визуализации всего этого;

Пример входных данных 1 (X являются выбранные плитки):

[X][X][X][ ][ ] 
[ ][X][X][ ][ ] 
[ ][ ][X][ ][ ] 
[ ][ ][X][ ][ ] 
[ ][ ][ ][ ][ ] 

Результат 1:

true 

---

Пример ввода 2 (X являются выбранные плитки):

[X][X][X][ ][ ] 
[ ][X][X][ ][ ] 
[ ][ ][ ][X][X] 
[ ][ ][ ][ ][ ] 
[ ][ ][ ][ ][ ] 

Пример вывода 2:

false 

---

Я думал, сравнивая все плитки всех остальных один за другим, и предположить, что плитки были связаны, если все плитки были связаны, по крайней мере, один другой плитки, но понял, что это не так работать, потому что это было бы вернуть истинное что-то вроде этого:

[X][X][ ][ ][ ] 
[ ][ ][ ][ ][ ] 
[ ][ ][ ][ ][ ] 
[ ][ ][X][X][ ] 
[ ][ ][ ][ ][ ] 

---

Я не мог придумать, как сделать это, и я не мог найти решение для такой задачи в Интернете.

Answer 1

Тип алгоритма заполнения заливки; берет один из фрагментов и рекурсивно расходует соседние плитки в выборе. Если все плитки в выборе были использованы таким образом, все выбранные плитки подключены.

boolean isConnected(List<Tile> selection) { 

    if (selection.isEmpty()) 
     return true; // ????? 

    Queue<Tile> toConsume = new LinkedList<>(selection); 
    Queue<Tile> queue = new LinkedList<>(); 
    queue.add(toConsume.remove()); 

    while (!queue.isEmpty() && !toConsume.isEmpty()) { 
     Tile tile = queue.remove(); 
     findNeighbours(tile, toConsume) 
     .forEach(n -> { 
      toConsume.remove(n); 
      queue.add(n); 
     }); 
    } 
    return toConsume.isEmpty(); 
} 

List<Tile> findNeighbours(Tile tile, Collection<Tile> tiles) { 
    return tiles.stream() 
     .filter(t -> distance(t, tile) == 1) 
     .collect(Collectors.toList()); 
} 

int distance(Tile a, Tile b) { 
    int dx = a.getX() - b.getX(); 
    int dy = a.getY() - b.getY(); 
    return Math.abs(dx) + Math.abs(dy); 
}