使用深度优先搜索的形状分割

本文介绍了使用深度优先搜索的形状分割的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何在深度优先搜索中解决此问题:

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.