基于二维网格数组上单元格值的路径查找

Question

我有一个由JLabel组成的网格。每个单元有3种状态:公共枚举令牌{ VIDE，CERCLE_ROUGE，CERCLE_BLEU }空单元== Token.VIDE。

我有一个简单的算法，它可以查找给定单元格的所有邻居，然后使用swing自定义绘画来绘制一个多边形，该路径以标签的中心作为点。

private CellsList getNeighbors(int  row, int col) {
    CellsList neighbors = new CellsList();
    for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1  ) {
        for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1  ) {
            if(!((colNum == col) && (rowNum == row))) {
                if(withinGrid (rowNum, colNum )  ) {
                    neighbors.add( new int[] {rowNum, colNum});
                }
            }
        }
    }

    return neighbors;
}

下面是有路径的条件：

if((size() >= MIN_PATH_LEGTH) && neighbors.contains(origin)  ) {
            add(cell);
            return true;
        }

现在，我想通过添加这样的条件来使它更加精确，比如路径可以有效，只要至少有4个单元格在邻域中找到相同的值，并且至少有一个相反的值。

示例：(11，10)(10，11)(11，12)(12，11)上的红细胞可以形成有效路径，只要在(11，11)上至少有一个蓝细胞。(见下图)

​

​

以下内容不能是有效的路径，因此没有绘图：

​

​

现在，算法只使用我定义的最小值(int MIN_PATH_LEGTH = 3)找到一条路径，但我无法找到一种方法来定义第二个条件(在邻域内至少有一个相反的单元格值)

如果需要，我将使用新元素进行编辑。

Answer 1

我的答案是基于在先前的回答中发布的代码。

路径类

添加isWithinLoop以检查单元格是否在路径内，方法是检查其左侧、右侧、顶部和底部是否有路径单元格。

还添加了getContainedWithin，它返回所有受路径限制的单元格的集合，它们的标记与路径的颜色相反。

    //returns a collection of all cells that are bounded by the path 
    //and their token is of the opposite color of the path 
    List<int[]> getContainedWithin() {

        //find path max and min X values, max and min Y values
        minPathRow = grid[0].length; //set min to the largest possible value
        maxPathCol = grid.length;
        maxPathRow = 0;              //set max to the largest possible value
        maxPathCol = 0;

        //find the actual min max x y values of the path
        for (int[] cell : this) {
            minPathRow = Math.min(minPathRow, cell[0]);
            minPathCol = Math.min(minPathCol, cell[1]);
            maxPathRow = Math.max(maxPathRow, cell[0]);
            maxPathCol = Math.max(maxPathCol, cell[1]);
        }

        //todo remove after testing
        System.out.println("x range: "+minPathRow + "-" 
        + maxPathRow + " y range: " + minPathCol + "-" + maxPathCol);

        List<int[]> block = new ArrayList<>(25);
        int[] cell = get(0);//get an arbitrary cell in the path
        Token pathToken = grid[cell[0]][cell[1]]; //keep a reference to its token

        //iterate over all cells within path x, y limits
        for (int col = minPathCol; col < (maxPathCol); col++) {

            for (int row = minPathRow; row < (maxPathRow); row++) {

                //check cell color
                Token token = grid[row][col];
                if ((token == pathToken) || (token == Token.VIDE)) {
                    continue;
                }
                if (isWithinLoop(row,col)) {
                    block.add(new int[] {row, col});
                }
            }
        }

        return block;
    }

    //check if row, col represent a cell with in path by checking if it has a 
    //path-cell to its left, right, top and bottom 
    private boolean isWithinLoop(int row, int col) {

        if(  isPathCellOnLeft(row, col)
             &&
             isPathCellOnRight(row, col)
             &&
             isPathCellOnTop(row, col)
             &&
             isPathCellOnBottom(row, col)
          ) {
            return true;
        }

        return false;
    }

    private boolean isPathCellOnLeft(int cellRow, int cellCol) {

        for ( int col = minPathCol; col < cellCol ; col++) {

            if(getPath().contains(new int[] {cellRow, col})) {
                return true;
            }
        }

        return false;
    }

    private boolean isPathCellOnRight(int cellRow, int cellCol) {

        for ( int col = cellCol; col <= maxPathCol ; col++) {

            if(getPath().contains(new int[] {cellRow, col})) {
                return true;
            }
        }

        return false;
    }

    private boolean isPathCellOnTop(int cellRow, int cellCol) {

        for ( int row =minPathRow; row < cellRow ; row++) {

            if(getPath().contains(new int[] {row, cellCol})) {
                return true;
            }
        }

        return false;
    }

    private boolean isPathCellOnBottom(int cellRow, int cellCol) {

        for ( int row = cellRow; row <= maxPathRow; row++) {

            if(getPath().contains(new int[] {row, cellCol})) {
                return true;
            }
        }

        return false;
    }
}

模型类

添加一个getter方法来访问getContainedWithin

List<int[]> getContainedWithin() {

    return (path == null ) ? null : path.getContainedWithin();
} 

控制类

如果ModelListener为空，则更新getContainedWithin以忽略路径：

private class ModelListener implements PropertyChangeListener {
        @Override
        public void propertyChange(PropertyChangeEvent evt) {
            IndexedPropertyChangeEvent iEvt = (IndexedPropertyChangeEvent)evt;
            int index = iEvt.getIndex();
            int row = index / Model.COLS;
            int col = index % Model.COLS;
            Token token = (Token) evt.getNewValue();

            SwingUtilities.invokeLater(new Runnable() {

                @Override
                public void run() {

                    view.setCell(token, row, col);
                    CellsList path = model.getPath();
                    //ignore path if null, empty or encloses no cell
                    if((path == null) || path.isEmpty()
                                        || model.getContainedWithin().isEmpty()) {
                        return;
                    }
                    view.addPath(path);
                    view.refresh();
                }
            });
        }
    }

可以下载此存储库的完整代码。

Answer 2

在调用此方法之前进行测试，如果redCell的路径确定：

public boolean isThereABlueCellWithinMyRedPath() {
    // height = height of your map
    // width = width of yout map
    // this array is suppose to be in an other place...
    Cell[][] cellArray = new Cell[height][width];
    // ... so are those two lists
    List<Cell> blueCellsList = new ArrayList<>();
    List<Cell> redCellsList = new ArrayList<>();

    //foreach blueCell on the map ...
    for (Cell blueCell : blueCellsList) {
        boolean north = false;
        boolean east = false;
        boolean south = false;
        boolean west = false;
        int originX = blueCell.getX();
        int originY = blueCell.getY();

        // ... if there is a redCell at north...
        for (int i = originY; i >= 0; i--) {
            if (redCellsList.contains(cellArray[originX][i])) {
                north = true;
                break;
            }
        }
        // ... East ...
        for (int i = originX; i < cellArray[originX].length; i++) {
            if (redCellsList.contains(cellArray[i][originY])) {
                east = true;
                break;
            }
        }
        // ... South ...
        for (int i = originY; i < cellArray.length; i++) {
            if (redCellsList.contains(cellArray[originX][i])) {
                south = true;
                break;
            }
        }
        // ... West ...
        for (int i = originX; i >= 0; i--) {
            if (redCellsList.contains(cellArray[i][originY])) {
                west = true;
                break;
            }
        }
        // ... I am surrended by redCell
        if (south && east && north && west)
            return true;
    }
    return false;
}

我没有尝试这段代码，但它似乎奏效了。

Answer 3

也许您可以列出一个蓝色单元格和红色单元格的列表，如果您想测试红色细胞的路径中是否有一个蓝色单元格，您可以：

去北方，直到你遇到一个redCell或地图限制:如果这是你用下一个blueCell测试的地图限制，那你就回到你的位置，在东部、南部和西部也一样。如果你先在4面找到一个redCell，你会返回真，否则你会返回假。

如果你想在一个很小的地图上进行测试，这就足够了。但是如果红细胞的形状是免费的，我就找不到更好的方法了。