检查二维矩阵上的所选图块是否全部连接
Checking if chosen tiles on a 2d matrix are all connected
我正在创建一个游戏,其地图是 [100 tile x 100 tile] 矩阵。玩家可以通过组合 4 个方块来创建 "Duchies"。游戏会让玩家选择 4 个方块并检查这些方块是否全部相互连接,只有当它们连接在一起时才允许玩家创建公国。
所以我的 isConnected()
方法将采用 ArrayList<Tiles>
并且瓷砖有 getX()
和 getY()
方法,其中 return 是它们的 X 和 Y网格上的坐标。如果瓷砖相互连接,则 return 为真,否则为假。 注意瓷砖不能对角连接。
值得一提的是,该方法将需要对 ArrayList 中超过 4 个图块的图块起作用,因为它需要检查更大的图块列表,而 Duchy 场景是如何使用该方法的示例.
只是为了形象化整个事情;
示例输入 1(X 是选定的图块):
[X][X][X][ ][ ]
[ ][X][X][ ][ ]
[ ][ ][X][ ][ ]
[ ][ ][X][ ][ ]
[ ][ ][ ][ ][ ]
示例输出 1:
true
示例输入 2(X 是选定的图块):
[X][X][X][ ][ ]
[ ][X][X][ ][ ]
[ ][ ][ ][X][X]
[ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
示例输出 2:
false
我想过将所有图块与所有其他图块一一比较,并假设如果所有图块都连接到至少一个其他图块,则所有图块都已连接,但我意识到这是行不通的,因为它会 return 对这样的事情是正确的:
[X][X][ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][X][X][ ]
[ ][ ][ ][ ][ ]
我想不出解决这个问题的方法,也找不到在线解决此类问题的方法。
有点像洪水填充算法;获取其中一个图块并递归地消耗选择中的相邻图块。如果选择中的所有图块都以这种方式消耗,则所有选定的图块都已连接。
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);
}
我正在创建一个游戏,其地图是 [100 tile x 100 tile] 矩阵。玩家可以通过组合 4 个方块来创建 "Duchies"。游戏会让玩家选择 4 个方块并检查这些方块是否全部相互连接,只有当它们连接在一起时才允许玩家创建公国。
所以我的 isConnected()
方法将采用 ArrayList<Tiles>
并且瓷砖有 getX()
和 getY()
方法,其中 return 是它们的 X 和 Y网格上的坐标。如果瓷砖相互连接,则 return 为真,否则为假。 注意瓷砖不能对角连接。
值得一提的是,该方法将需要对 ArrayList 中超过 4 个图块的图块起作用,因为它需要检查更大的图块列表,而 Duchy 场景是如何使用该方法的示例.
只是为了形象化整个事情;
示例输入 1(X 是选定的图块):
[X][X][X][ ][ ]
[ ][X][X][ ][ ]
[ ][ ][X][ ][ ]
[ ][ ][X][ ][ ]
[ ][ ][ ][ ][ ]
示例输出 1:
true
示例输入 2(X 是选定的图块):
[X][X][X][ ][ ]
[ ][X][X][ ][ ]
[ ][ ][ ][X][X]
[ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
示例输出 2:
false
我想过将所有图块与所有其他图块一一比较,并假设如果所有图块都连接到至少一个其他图块,则所有图块都已连接,但我意识到这是行不通的,因为它会 return 对这样的事情是正确的:
[X][X][ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][X][X][ ]
[ ][ ][ ][ ][ ]
我想不出解决这个问题的方法,也找不到在线解决此类问题的方法。
有点像洪水填充算法;获取其中一个图块并递归地消耗选择中的相邻图块。如果选择中的所有图块都以这种方式消耗,则所有选定的图块都已连接。
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);
}