在网格中查找特定形状

Question

我有一个二维数组作为网格（大小为 9x9），想在其中找到几个特定的形状：

XXX XXX  X
 X  X   XXX
 X  X    X

在我搜索这些并将它们从网格中删除之后，我想搜索 3/4/5 长的直线。注意：此形状的所有元素必须具有相同的颜色。

显然，我可以将这些硬编码或通过暴力破解的方式来找到它们，但我正在寻找一种算法，它可以在可行的时间内找到这些形状。

这是我用于查找和删除直线的代码。作为输出，我期望在此过程中删除的元素数量。它有效（大部分时间......如果你能告诉我如何将 horizontal/vertical 组合成一个，那么奖励加分，但那是另一天的话题）：

private Cell[][] field;

/**
 * Removes a given list of stones from the field and 
 * fills the slots with empty ones.
 * 
 * @param list 
 */
private void removeStones(ArrayList<int[]> list) {
    for(int i = 0; i < list.size(); i++) {
        field[list.get(i)[1]][list.get(i)[0]] = new Cell(Color.NONE, Attribute.NONE);
    }
}

/**
 * Check the gamefield for valid straight structures and remove them.
 * 
 * @return The amount of stones removed.
 */
private int checkStraight() {
    Color curr = Color.NONE;
    int counter = 0;
    int total = 0;
    /* Holds the coordinates of the shape being processed currently */
    ArrayList<int[]> stones = new ArrayList<>();

    // Horizontal 
    for(int y = 0; y < getSize(); y++) {
        for(int x = 0; x < getSize(); x++) {
            if(curr == getCell(x, y).getBlock().getColor() 
                    && getCell(x, y).isGem()) {
                counter++;
                stones.add(new int[] {x, y});
            }             
            else {
                if(counter > 2) {
                    total += counter;
                    removeStones(stones);
                    /* Debugging Info */
                    stones.forEach((a)->System.out.println("[" + a[0] + "," + a[1] + "]"));
                    System.out.println("");
                }
                counter = 1;
                curr = getCell(x, y).getBlock().getColor();
                stones = new ArrayList<>();
                stones.add(new int[] {x, y});
            }
        }
        curr = Color.NONE;
        counter = 0;
    }

    // Vertical
    for(int x = 0; x < getSize(); x++) {
        for(int y = 0; y < getSize(); y++) {
            if(curr == getCell(x, y).getBlock().getColor() 
                    && getCell(x, y).isGem()) {
                counter++;
                stones.add(new int[] {x, y});
            }             
            else {
                if(counter > 2) {
                    total += counter;
                    removeStones(stones);
                    /* Debugging Info */
                    stones.forEach((a)->System.out.println("[" + a[0] + "," + a[1] + "]"));
                    System.out.println("");
                }
                counter = 1;
                curr = getCell(x, y).getBlock().getColor();
                stones = new ArrayList<>();
                stones.add(new int[] {x, y});
            }
        }
        curr = Color.NONE;
        counter = 0;
    }

    return total;
}

/**
 * Return cell at col/row.
 *
 * @param col
 * @param row
 * @return The cell at position col/row.
 */
public Cell getCell( int col, int row ) {
    return field[row][col];
}

/**
 * Return the grid size.
 *
 * @return The size of the grid.
 */
public int getSize() {
    return field.length;
}

如果您需要有关细胞结构的更多信息，或需要澄清某些东西应该如何工作的信息，请直接询问，我会提供更多信息。

Answer 1

以防万一有人遇到和我一样的问题，我想分享一下我最终是如何解决这个问题的。

我做了一个函数来寻找给定的形状（在我的例子中，我总是需要检查 3x3 正方形中的 5 个位置，但你可以随意调整它），然后将结果模式与内容进行比较网格和 return 找到的位置

然后调用此函数 4 次以找到一个 'L-Shape'，方法是输入任意旋转的基本 L 形以在给定位置找到它。

/**
* Find the structure specified in p1, p2, p3, p4 and p5 rotated by 90
* degrees rot times
*
* @param x   X-Position of the structure
* @param y   Y-Position of the structure
* @param rot How many times to rotate by 90 degrees
* @param p1  A piece of the structure (Coordinates)
* @param p2  A piece of the structure (Coordinates)
* @param p3  A piece of the structure (Coordinates)
* @param p4  A piece of the structure (Coordinates)
* @param p5  A piece of the structure (Coordinates)
* @return The ArrayList containing all found stones
*/
private ArrayList<int[]> findStructure( int x, int y, int rot, int[] p1, int[] p2, int[] p3, int[] p4, int[] p5 ) {
    ArrayList<int[]> stones = new ArrayList<>();

    /* Rotate shape by 90 degrees rot times */
    for( int i = 1; i <= rot; i++ ) {
        /* Rotate 90 degress */
        p1 = new int[]{-p1[1], p1[0]};
        p2 = new int[]{-p2[1], p2[0]};
        p3 = new int[]{-p3[1], p3[0]};
        p4 = new int[]{-p4[1], p4[0]};
        p5 = new int[]{-p5[1], p5[0]};
    }

    // Do stuff and see if your pattern matches the actual grid content
    // ...

    return stones;
}

在网格中查找特定形状

Finding a certain shape in grid

java

algorithm

grid

shape