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

Question

如何在深度优先搜索中解决这个问题：

6x6 正方形，沿着格子的边缘切成两部分。
要求两部分的形状完全一致

试算一下e：一共有多少种不同的切分方法

注：旋转对称属于同一种分割方法

例如：

抱歉，看来我只是想不假思索地寻找答案。其实我想了很多。原题目没有要求深度优先搜索，我觉得需要用它来解决这个问题，但是我没有一个明确的思路。我觉得满足要求就是格子之间是连续的，但是不知道怎么表达这种情况。

Answer 1

我觉得用dfs这个idea不错。您可以在一个清晰（没有墙壁）的迷宫中开始搜索。
在任意单元格上开始搜索。
对于探索的每个单元格：将对称单元格标记为 "wall"。

找到一个分段的伪代码可以是：

    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 寻找 one 分割的摆动演示：

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; }
}

点击将其设置为原点并开始搜索。再次点击同一个单元格可以看到不同的分割。

Answer 2

我看到一个解决这个问题的方法，就是从划分网格的直线开始搜索，代码如下：

public class Maze {

int point[][] = new int[10][10]; // The intersection between the line and the line
int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}}; // get Neighbors
static int N = 6; // default size 
static int count = 0; 

public void dfs(int x, int y) {
    if (x == 0 || y == 0 || x == N || y == N) {
        count++;
        return;
    }

    for(int i = 0; i < 4; i++) {
        int n = x + dir[i][0];
        int m = y + dir[i][1];

        if (n < 0 || n > N || m < 0 || m > N) { continue; }
        if (point[n][m] == 0) {
            point[n][m] = 1;
            point[N-n][N-m] = 1;
            dfs(n, m);
            point[n][m] = 0;
            point[N-n][N-m] = 0;
        }
    }
}

public static void main(String[] args) {
    Maze test = new Maze();
    test.point[N/2][N/2] = 1; // Search from the center point
    test.dfs(N/2, N/2);
    System.out.println(count/4); // There are four types of rotational symmetry
} }

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

Shape segmentation using Depth-First-Search

algorithm

depth-first-search