算法找到最大面積

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; 
} 

}