时间戳

首页 > 解决方案 > 对扇区中的细胞进行计数

java - 对扇区中的细胞进行计数

问题描述

问题陈述 - 计算扇区中的单元格

考虑一个二维网格的单元格，每个单元格可能是空的或填充的。连接的填充单元形成一个扇区。如果两个单元在水平、垂直或对角线上彼此相邻，则称它们是连接的。网格上可能有多个扇区。你的工作是在网格上找到最大的扇区（就单元数而言）。

网格以 0 和 1 的二维数组形式给出，每个数组由 0 和 1 组成。1 表示单元格已填充，0 表示单元格为空。

下面的 2D 数组说明了一个具有 3 个扇区的网格（最大的包含 5 个单元格）。

确定给定网格的最大扇区的大小。

class Cell {
    int value;
    boolean checked;
    Cell(int value,boolean checked) {
        this.value = value;
        this.checked = checked;
    }
}

public class CountSectorSize {
    int traverseGrid(Cell[][] a) {
        int tempSectorSize, sectorSize = 0;
        // Cell[][] a = null;
        for (int i = 0; i < a.length; ++i)
            for (int j = 0; j < a[i].length; ++j) {
                if ((a[i][j].value == 0) || (a[i][j].checked == true))
                    continue;
                else {
                    tempSectorSize = findSectorSize(a, i, j);
                    System.out.println (tempSectorSize);
                    if (tempSectorSize > sectorSize)
                        sectorSize = tempSectorSize;
                    ++j;
                }
            }
        return sectorSize;
    }
int findSectorSize(Cell[][] a, int i, int j) {
    if ((i >= 0) && (i < a.length) && (j >= 0) && (j < a[i].length)) { // Check
        // Boundaries check
        if ((a[i][j].value == 0) || (a[i][j].checked == true))
            return 0;
        else {
            a[i][j].checked = true;
            int thisCellScore = 1;
            //Calling adjacent cells on the top, bottom and right of the cell as other cell would have been covered in previous calls.
            int top = findSectorSize(a, i - 1, j);
            int topRight = findSectorSize(a, i - 1, j + 1);
            int after = findSectorSize(a, i, j + 1);
            int bottomRight = findSectorSize(a, i + 1, j + 1);
            int bottom = findSectorSize(a, i + 1, j);
            return thisCellScore+ top + topRight + after + bottomRight
                    + bottom;
        }
    } else {
        return 0;
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    CountSectorSize countSectorSize = new CountSectorSize();
    // Sample Grid
    Cell[][] sample = {{new Cell(1,false),new Cell(0,false),new Cell(0,false),new Cell(1,false),new Cell(1,false)},
            {new Cell(1,false),new Cell(1,false),new Cell(0,false),new Cell(0,false),new Cell(1,false)},
            {new Cell(0,false),new Cell(1,false),new Cell(0,false),new Cell(0,false),new Cell(1,false)},
            {new Cell(1,false),new Cell(1,false),new Cell(1,false),new Cell(0,false),new Cell(1,false)},
            {new Cell(1,false),new Cell(0,false),new Cell(0,false),new Cell(0,false),new Cell(1,false)},
            {new Cell(1,false),new Cell(1,false),new Cell(0,false),new Cell(0,false),new Cell(1,false)},
            {new Cell(0,false),new Cell(1,false),new Cell(0,false),new Cell(0,false),new Cell(1,false)},
            {new Cell(1,false),new Cell(1,false),new Cell(0,false),new Cell(0,false),new Cell(0,false)}};
    System.out.println("Final Result \t "+countSectorSize.traverseGrid(sample));
    }
}

在 main 方法中输入这个样本，我应该得到 13 作为输出。但实际输出为 8。不胜感激。

标签： javaarraysalgorithmrecursion

解决方案

需要递归调用所有相邻的单元格，因为您无法确定当前调用所在的单元格的位置。尝试添加

            int bottomLeft = findSectorSize(a, i + 1, j - 1);
            int before = findSectorSize(a, i, j - 1);
            int topLeft = findSectorSize(a, i - 1, j - 1);
            return thisCellScore + top + topRight + after + bottomRight
                    + bottom + bottomLeft + before + topLeft;

推荐阅读