java - 查看电路是否断路的函数(二维数组)

Question

我想创建一个函数，让我通过返回 true 或 false 来查看我存储在 2D 数组中的电路是否存在断点。为了简单起见，我使用 1 和 0 对电路进行建模。其中 1 是组件，0 是空格。我尝试过使用递归函数，但没有成功，并且在这一点上几乎陷入困境。

例如:

1 1 1

1 0 1

1 1 1

我希望它返回 true，因为所有 1 都是串联的。这个二维数组将被可视化 as seen here .

1 1 1

0 0 1

1 1 1

我希望它返回 false，因为电路中有一个中断 as shown here .

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

我当前的代码如下所示。当我使用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 个连接应该适合您的用例，因为我们只查找串联连接。

您只需检查阵列并确保所有活细胞都有 2 个且只有 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 中的字段应该是私有(private)的(甚至可能是最终的)，并且您应该通过 getters 访问它们。