算法找到最大面积

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. 
................................ 

寻找算法找到最大面积。这里，“区域”被定义为由Xs界定的点（。）的数量。

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. 将文件加载到char [] []中。 （1个字符[]每行）
2. 遍历炭[] []（2维）
3. 在找到一个 ' '执行flood fill，改变所有'。'到'，'，每增加一个计数器。
4. 在洪水填充结束时，将此计数器与全局设置的最大值进行比较。如果它更高，则将其设置为新的最高值。

返回您设置的最高值。

如果你有一个Java实现的任何具体问题，然后让我知道

Geobits：

注意：如果您要排除的区域“外”的任何盒，通常为 ，但在填充期间丢弃任何碰到边缘的区域（跳过 步骤2.2）。

当进行泛洪填充时，您有2种类型的边界。墙（'X'）和阵列的边缘（您需要明确检查以避免OutOfBounds异常）。如果你超出界限，继续填充，但设置一个标志，以便稍后知道不考虑为最大框指定的数量。

Answer 2

这是一个算法，它是洪水填充的替代方案。这种方法扫过二维数组，每遇到一个位于左侧（右侧，顶部，底部）之外的节点（像素），它会将当前节点标记为外部，即如果您的邻居在“外部”，则标记为'外面'。

该算法继续这样，直到没有更多的更新。这意味着所有可从“外部”访问的节点都已被标记。顺便说一句，这是一个非常类似的问题，水平集函数和更新它们（也使用洪水填充）。这种方法的好处在于它非常适合并行化。

1. Load 2D Symbol Array from File 
2. hasupdates = false 
3. Create 'isinside' bool array -> { 
     if(symbolarray[row][col] == '.' and row or col is at boundary) 
      isinside[row][col] = false 
     else 
      isinside[row][col] = true 
    } 

4. do{ 
    Do a sweep from left to right (for all rows) -> //This loop can be run parallely on all rows. 
     If (!isinside[row][col-1] and symbolarray[row][col] == '.'){ 
      isinside[row][col] = false //mark current value as 'outside' 
      hasupdates = true 
     } 
    Do similar sweeps from right to left, top to bottom(all columns) and bottom to top. 

}while(hasupdates) 

5. Go through 'isinside' array and count the number of falses. 

如果你有，你必须做这个面积计算巨大的文件，你可以沿行和列的扫描平行运行，因为每一行的更新（列更新）是独立于其他更新。

Answer 3

我得到了这是在采访过程中分配，这是编译和运行代码

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.HashSet; 
import java.util.Iterator; 
import java.util.Set; 

public class FindArea { 
public static void main(String[] args) 
{ 
    String fileName="C:\\map.txt"; 
    FindArea area = new FindArea(); 
    try{ 
     FileReader inputFile = new FileReader(fileName); 
     BufferedReader bufferReader = new BufferedReader(inputFile); 

     char[][] twoArray= new char[100][100]; 
     String line; 
     int i=0; 

     while ((line = bufferReader.readLine()) != null) { 
      twoArray[i] = line.toCharArray(); 
      System.out.println(line); 
      i++; 
     } 
     bufferReader.close(); 

     System.out.println("file read"); 
     System.out.println("Max area: " + area.getMaxArea(twoArray)); 

    } catch(Exception e) { 
     System.out.println("error : " + e.getMessage()); 
    } 
} 

/** 
* Get the maximum area from the given map 
* 
* @param charArray 
* @return 
*/ 
private int getMaxArea(char[][] charArray) { 
    HashMap<Integer, ArrayList<String>> numberOfBoxes = convertToBoxes(charArray); 

    numberOfBoxes = mergeOverlapAreas(numberOfBoxes); 

    int largeSize = 0; 
    for (Integer key : numberOfBoxes.keySet()) { 
     ArrayList<String> list = numberOfBoxes.get(key); 
     System.out.println("Key : " + key + " Size : " + list.size()); 
     if (largeSize < list.size()) { 
      largeSize = list.size(); 
     } 
    } 
    return largeSize; 
} 

/** 
* Convert the 2d Array to HashMap 
* Key being the count of boxes and 
* Value being the list of indexes associations 
* 
* @param charArray 
* @return 
*/ 
private HashMap<Integer, ArrayList<String>> convertToBoxes(char[][] charArray) { 
    HashMap<Integer, ArrayList<String>> numberOfBoxes = new HashMap<Integer, ArrayList<String>>(); 
    int boxes = 0; 

    for(int i=1; i<charArray.length; i++) { 

     for (int j=0; j<charArray[i].length; j++) { 

      if (charArray[i][j] == '.') { 

       boolean isExists = false; 

       for(Integer key : numberOfBoxes.keySet()) { 

        ArrayList<String> arrList = numberOfBoxes.get(key); 

        if(arrList != null) { 

         if(arrList.contains((i-1) + "-" + j) || 
          arrList.contains(i + "-" + (j-1))) { 

          isExists = true; 
          arrList.add(i + "-" + j); 
          numberOfBoxes.put(key, arrList); 
         } 
        } 
       } 

       if (!isExists) { 
        ArrayList<String> list = new ArrayList<String>(); 
        list.add(i + "-" + j); 
        numberOfBoxes.put(boxes, list); 
        boxes++; 
       } 
      } 
     } 
    } 
    return numberOfBoxes; 
} 

/** 
* Check for the points exists in more than one area 
* @param numberOfBoxes 
* @return 
*/ 
private HashMap<Integer, ArrayList<String>> mergeOverlapAreas(HashMap<Integer, ArrayList<String>> numberOfBoxes) { 

    for(Integer key : numberOfBoxes.keySet()) { 
     ArrayList<String> list1 = numberOfBoxes.get(key); 

     for (Integer key2 : numberOfBoxes.keySet()) { 

      if (key < key2) { 

       ArrayList<String> list2 = numberOfBoxes.get(key2); 
       Iterator<String> listIter = list2.iterator(); 

       while(listIter.hasNext()) { 

        if (list1.contains(listIter.next())) { 
         list1.addAll(list2); 
         Set<String> noDuplicates = new HashSet<String>(list1); 
         numberOfBoxes.put(key, new ArrayList<String>(noDuplicates)); 
         break; 
        } 
       } 
      } 
     } 

    } 
    return numberOfBoxes; 
} 

}