函数，以查看电路是否有中断(2D数组)。

Question

我想要创建一个函数，让我可以通过返回true或false来查看我存储在2D数组中的电路是否有中断。为了简单起见，我用1s和0s对电路进行了建模，其中1是部件，0是空间。然而，我尝试过处理递归函数，但没有效果，而且在这一点上我几乎被困住了。

例如：

1 1 1

1 0 1

1 1 1

我希望这个返回真，因为所有的1是串联的。这个二维数组将是可视化的如图所示。

1 1 1

0 0 1

1 1 1

我希望这回假，因为有一个中断在电路作为如图所示。

任何解决方案或指导将不胜感激！

我的当前代码如下所示。当我使用completeCircuit作为输入时，它返回的是不完整的，而当我将incompleteCircuit作为输入时，它返回完全。

    public class TraversalTest
    {
    boolean complete = false;
    int runs = 0;

    public static void main(String[] args)
    {
        TraversalTest traversal = new TraversalTest();
    }

    public TraversalTest()
    {
        Cell[][] completeCircuit =
            {
                { new Cell( 0,  0,  1), new Cell(   1,  0,  1), new Cell(   2,  0,  1) }, 
                { new Cell( 0,  1,  1), new Cell(   1,  1,  0), new Cell(   2,  1,  1) },
                { new Cell( 0,  2,  1), new Cell(   1,  2,  1), new Cell(   2,  2,  1) }
            };

        Cell[][] incompleteCircuit =
            {
                { new Cell( 0,  0,  1), new Cell(   1,  0,  1), new Cell(   2,  0,  1) }, 
                { new Cell( 0,  1,  0), new Cell(   1,  1,  0), new Cell(   2,  1,  1) },
                { new Cell( 0,  2,  1), new Cell(   1,  2,  1), new Cell(   2,  2,  1) }
            };

        completeCircuit[1][0].connected = true;
        int cellsLeft = (numOfPositiveCells(completeCircuit));

        checkComplete(completeCircuit, completeCircuit[1][0], cellsLeft);


        incompleteCircuit[1][0].connected = true;
        int cellsLeft1 = (numOfPositiveCells(incompleteCircuit));

        checkComplete(incompleteCircuit, incompleteCircuit[1][0], cellsLeft1);
    }

    void checkComplete(Cell[][] circuit, Cell currentCell, int cellsLeft)
    {
        currentCell.connected = true;

        if(cellsLeft > 0)
        {
            if(currentCell.x != 0 && circuit[currentCell.x-1][currentCell.y].value == 1 && 
                    circuit[currentCell.x-1][currentCell.y].connected == false)
            {
                cellsLeft--;
                checkComplete(circuit, circuit[currentCell.x-1][currentCell.y], cellsLeft);
            }
            else if(currentCell.x != 2 &&circuit[currentCell.x+1][currentCell.y].value == 1 && 
                    circuit[currentCell.x+1][currentCell.y].connected == false)
            {
                cellsLeft--;
                checkComplete(circuit, circuit[currentCell.x+1][currentCell.y], cellsLeft);
            }
            else if(currentCell.y != 0 && circuit[currentCell.x][currentCell.y-1].value == 1 && 
                    circuit[currentCell.x][currentCell.y-1].connected == false)
            {
                cellsLeft--;
                checkComplete(circuit, circuit[currentCell.x][currentCell.y-1], cellsLeft);
            }
            else if(currentCell.y != 2 && circuit[currentCell.x][currentCell.y+1].value == 1 && 
                    circuit[currentCell.x][currentCell.y+1].connected == false)
            {
                cellsLeft--;
                checkComplete(circuit, circuit[currentCell.x][currentCell.y+1], cellsLeft);
            }
            else
            {
                complete = false;
                System.out.println("Incomplete");
            }
        }
        else
        {
            complete = true;
            System.out.println("Complete");
        }
    }

    int numOfPositiveCells(Cell[][] circuit)
    {
        int num = 0;
        for(int x=0; x < 3; x++)
            for(int y=0; y < 3; y++)
                if(circuit[x][y].value == 1)
                    num++;
        return num;
    }
}

class Cell
{
    public boolean connected;
    public int value;
    public int x;
    public int y;

    public Cell(int x, int y, int value)
    {
        this.x = x;
        this.y = y;
        this.value = value;
    }
}

Answer 1

我认为检查每个单元格是否有2个连接应该适用于您的用例，因为我们只查找系列连接。

您只需遍历数组，并确保所有活动单元格都有两个并且只有两个活单元连接到它。

我建议你做一个专门的课程，这样你就不必在所有的方法中不停地通过电路了：

class CircuitChecker {
    private final Cell[][] circuit;
    private final int nbRows, nbCols;

    public CircuitChecker(Cell[][] circuit) {
        this.circuit = circuit;
        this.nbRows = circuit.length;
        this.nbCols = circuit[0].length;
    }

    public boolean isCircuitComplete() {
        boolean isComplete = true;
        for(int col = 0; col<nbCols; col++) {
            for (int row = 0; row < nbRows; row++) {
                if(cellIsLive(col, row) && !cellHas2LiveConnections(col, row)) {
                    isComplete = false;
                    break;
                }
            }
        }
        return isComplete;
    }

    private boolean cellIsLive(int col, int row) {
        return circuit[row][col].value == 1;
    }

    private boolean cellHas2LiveConnections(int col, int row) {
        Cell left = col > 0 ? circuit[col-1][row] : null;
        Cell right = col < nbCols-1 ? circuit[col+1][row] : null;
        Cell up = row > 0 ? circuit[col][row-1] : null;
        Cell down = row < nbRows-1 ? circuit[col][row+1] : null;

        int nbConnections = Stream.of(left, right, up, down)
                .filter(Objects::nonNull)
                .mapToInt(c -> c.value)
                .sum();
        return nbConnections == 2;
    }
}

你这样称呼它：

new CircuitChecker(completeCircuit).isCircuitComplete();
new CircuitChecker(incompleteCircuit).isCircuitComplete();

还有一点，类Cell中的字段应该是私有的(甚至可能是最终的)，您应该通过getter访问它们。