使用深度优先搜索的形状分割 [英] Shape segmentation using Depth-First-Search
问题描述
如何在深度优先搜索中解决此问题:
How to solve this in Depth-First-Search:
- 6x6正方形，沿着晶格的边缘切成两部分.
- 两个部分的形状必须完全相同.
尝试计算 e:总共有多少种不同的细分方法.
Try to calculate: There are a total of how many different segmentation methods.
注意:旋转对称属于同一分割方法.
Note: Rotational symmetry belongs to the same segmentation method.
例如:
对不起，看来我只是在寻找答案而没有思考.其实，我想很多.原始标题不需要深度优先"搜索，我认为需要使用它来解决此问题，但是我没有一个明确的主意.我认为满足要求的是网格之间是连续的，但是我不知道如何表达这种情况.
Sorry, it looks like I'm just looking for an answer without thinking. Actually, I think a lot. The original title didn't require a Depth-First-Search, and I think it needs to be used to solve this problem, but I don't have a clear idea. I think that meet the requirements is between grid is continuous, but I don't know how to express this kind of situation.
推荐答案
我认为使用dfs的想法很好.您可以在干净(没有墙壁)的迷宫中开始搜索.
在任意单元格上开始搜索.
对于探索的每个单元格:将对称的单元格标记为墙".
I think the idea to use dfs is good. You could start the search on a clear (no walls) maze.
Start the search on an arbitrary cell.
For each cell explored : mark the symmetric one as "wall".
找到一个细分的伪代码可能是:
A pseudo code to find one segmentation could be:
boolean dfs(cell) {
if cell is not empty or was explores or null - return false
symCell = get Symetric Cell of cell
if symCell is not empty or was explores or null - return false
else mark symCell as wall
mark cell as explored
//loop over neighbors
for(Cell c : getNeighbors of cell){
if ( dfs(c) ) return true
}
return false
}
可以一次又一次地重复该过程以查找更多细分.
我还没有想到任何关于停止标准的好主意:您如何知道找到了所有可能的细分.
这是找到一个细分的简单的Java swing演示:
The process can be repeated over and over again to find more segmentations.
I did not come up yet with any good idea about a stop criteria: how do you know that all possible segmentations were found.
Here is a simple java swing demonstration of finding one segmentation:
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.GridLayout;
import java.awt.Point;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import javax.swing.BorderFactory;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
public class SwingMaze extends JFrame {
private JPanel mazePanel;
private Cell[][] cells;
private int mazeRows = 6, mazeCols = 6; //default size
public SwingMaze() { this(null); }
public SwingMaze(Cell[][] cells) {
this.cells = (cells == null) ?
getCells(mazeRows,mazeCols) : cells;
mazeRows = this.cells.length; mazeCols = this.cells[0].length;
setTitle("Grid");
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
buildUi();
pack();
setVisible(true);
}
void buildUi() {
mazePanel = new JPanel();
mazePanel.setLayout(new GridLayout(cells.length, cells[0].length));
add(mazePanel, BorderLayout.CENTER);
for (Cell[] cellsRow : cells) {
for (Cell cell : cellsRow) {
cell.addMouseListener(cellMouseListener(cell));
mazePanel.add(cell);
}
}
add(new JLabel("Click any cell to set it origin and start search"),
BorderLayout.SOUTH);
}
private MouseListener cellMouseListener(Cell cell) {
return new MouseAdapter() {
@Override
public void mouseClicked(MouseEvent e) {solve(cell);}
};
}
private List<Cell> getNeighbors(Cell cell){
List<Cell> neighbors = new ArrayList<>();
for(int row = (cell.getPosition().x -1) ;
row <= (cell.getPosition().x +1) ; row++) {
if(! validPosition (row,0)) { continue;}
for(int col = (cell.getPosition().y -1) ;
col <= (cell.getPosition().y +1) ; col++) {
if(! validPosition (row,col)) { continue;}
if((row == cell.getPosition().x) &&
(col == cell.getPosition().y) ) { continue;}
if((row != cell.getPosition().x) &&
(col != cell.getPosition().y) ) { continue;}
neighbors.add(cells[row][col]);
}
}
Collections.shuffle(neighbors);
return neighbors;
}
private boolean validPosition(int row, int col) {
return (row >= 0) && (row < mazeRows)
&& (col >= 0) && (col < mazeCols);
}
private Cell getSymetricCell(Cell cell) {
if(! validPosition(cell.getPosition().x,
cell.getPosition().y)) { return null; }
int row = mazeRows - cell.getPosition().x -1;
int col = mazeCols - cell.getPosition().y -1;
return cells[row][col];
}
private Cell[][] getCells(int rows, int cols) {
Cell[][] cells = new Cell[rows][cols];
for(int row=0; row <cells.length; row++) {
for(int col=0; col<cells[row].length; col++) {
cells[row][col] = new Cell();
cells[row][col].setPosition(row, col);
}
}
return cells;
}
boolean solve(Cell cell) {
reset();
return dfs(cell);
}
boolean dfs(Cell cell) {
if(cell == null){ return false; }
//if cell is wall, or was explored
if( !cell. isToBeExplored()) { return false; }
Cell symCell = getSymetricCell(cell);
if((symCell == null) || ! symCell.isToBeExplored()) { return false; }
symCell.setState(State.WALL);
cell.setState(State.WAS_EXPLORED);
//loop over neighbors
for(Cell c : getNeighbors(cell)){
if (dfs(c)) { return true; }
}
return false;
}
private void reset() {
for(Cell[] cellRow : cells) {
for(Cell cell : cellRow) {
cell.setState(State.EMPTY);
}
}
}
public static void main(String[] args) {
new SwingMaze();
}
}
class Cell extends JLabel {
Point position;
State state;
private static int cellH =65, cellW = 65;
Cell() {
super();
position = new Point(0,0);
state = State.EMPTY;
setBorder(BorderFactory.createLineBorder(Color.RED));
setPreferredSize(new Dimension(cellH , cellW));
setOpaque(true);
}
boolean isToBeExplored() { return state == State.EMPTY; }
Point getPosition() {return position;}
void setPosition(Point position) {this.position = position;}
void setPosition(int x, int y) { position = new Point(x, y); }
void setState(State state) {
this.state = state;
setBackground(state.getColor());
}
State getState() { return state; }
@Override
public String toString() {
return "Cell " + position.getX() + "-" + position.getY()+ " " + state ;
}
}
enum State {
EMPTY (Color.WHITE), WALL (Color.BLUE), EXPLORED(Color.YELLOW),
WAS_EXPLORED(Color.PINK);
private Color color;
State(Color color) { this.color = color; }
Color getColor() { return color; }
}
单击将其设置为原点并开始搜索.再次单击同一单元格以查看不同的细分.
Clicking will set it as origin and start search. Click the same cell again to see different segmentation.
这篇关于使用深度优先搜索的形状分割的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
