11 
................................
.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++;
    }
  }

これは私の最初のことであり、さらに進むのに苦労しています。

4

3 に答える 3

-1

フラッド フィルに代わるアルゴリズムを次に示します。このメソッドは 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.

この面積計算を行う必要がある巨大なファイルがある場合、各行の更新 (列の更新) は他の更新とは独立しているため、行と列に沿ってスイープを並行して実行できます。

于 2013-10-16T19:37:35.570 に答える