java - 寻找最大面积的算法

Question

................................
.XXXXXXXXXXXXXXX.....XXXXXXXXXX.
.X.....X.......X.....X........X.
.X.....X.......XXXXXXX........X.
.XXXXXXXXXXXX.................X.
.X....X.....X.................X.
.X....X.....XXXX..............X.
.XXXXXX........X..............X.
......X........X..............X.
......X........X..............X.
......X........X..............X.
......XXXXXXXXXXXXXXXXXXXXXXXXX.
................................

寻找一种算法来找到最大的区域。此处，“区域”定义为以 X 为界的点 (.) 数。

   private static void readFile(File inputFile) throws IOException {

    Scanner fileScanner = new Scanner(inputFile);

    Point previousPoint = null;

    int rowCount = 0;
    while(fileScanner.hasNext()){
        String line = fileScanner.next();

        String[] points = line.split(" ");

        for(int columnCount=0;columnCount<points.length;columnCount++){

            if(points[columnCount].equalsIgnoreCase("x")){
                Point currentPoint = new Point();
                currentPoint.setxValue(columnCount);
                currentPoint.setyValue(rowCount);
            }
        }

        rowCount++;
    }
  }

这是我的第一个，并且正在努力更进一步。

Answer 1

这个算法应该可行。您只需要用 Java 实现它。

1. Load the file into a char[][]. (1 char[] per line)
2. Loop through the char[][] (2 dimensionally)
   3. upon finding a '.', perform flood fill, changing all '.' to ',', also incrementing a counter on every change.
   4. At the end of flood fill, compare this counter with a globally set maximum. If it's higher, then set it as the new highest. (If the edges are not a proper boundary, then do not set this counter if you reached an edge during flood fill by setting a flag during 3)
3. Return the highest you set.

如果您对 Java 实现有任何具体问题，请告诉我

地理比特:

Note: If you want to exclude the area "outside" any boxes, flood as usual, but discard any area that hits the edge during the fill(skip step 2.2 for that flood).

进行洪水填充时，您有两种类型的边界。一堵墙('X')和数组的边缘(您需要明确检查以避免 OutOfBounds 异常)。如果你撞到了界外，继续填充，但设置一个标志，这样你以后就知道不要考虑你为最大盒子计算的数字。