8

衛星で撮影された表面の画像が表示されます。画像は、水が「。」でマークされているビットマップです。土地は''でマークされてい*ます。の隣接するグループが*島を形成します。（2つの' *'は、水平、垂直、または斜めに隣接している場合は隣接しています）。あなたの仕事は、ビットマップ内の島の数を印刷することです。

入力例：-

.........**
**......***
...........
...*.......
*........*.
*.........*

出力：-5

これが私の実装で、O(r * c)スペースとO(r * c)スペースを取ります。ここで、rは合計数です。行の数とcは列の総数です。

#include <stdio.h>
#define COLS 12

void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount)
{
    if((row < 0) || (row >= rowCount) || (col < 0) || (col >= COLS) || (map[row][col] != '*') || (visited[row][col] == 1)) return;

    visited[row][col] = 1;

    //calling neighbours
    markVisted(map, visited, row+1, col, rowCount);
    markVisted(map, visited, row, col+1, rowCount);
    markVisted(map, visited, row-1, col, rowCount);
    markVisted(map, visited, row, col-1, rowCount);
    markVisted(map, visited, row+1, col+1, rowCount);
    markVisted(map, visited, row-1, col-1, rowCount);
    markVisted(map, visited, row-1, col+1, rowCount);
    markVisted(map, visited, row+1, col-1, rowCount);
}
int countIslands(char map[][COLS], int visited[][COLS], int rowCount)
{
    int i, j, count = 0;
    for(i=0; i<rowCount; ++i){
        for(j=0; j<COLS; ++j){

            if((map[i][j] == '*') && (visited[i][j] == 0)){
                ++count;
                markVisted(map, visited, i, j, rowCount);
            }
        }
    }
    return count;
}

int main()
{
    char map[][COLS] = {
                    "*..........",
                    "**........*",
                    "...........",
                    "...*.......",
                    "*........*.",
                    "..........*"               
                    };
    int rows = sizeof(map)/sizeof(map[0]);
    int visited[rows][COLS], i, j;  

    for(i=0; i<rows; ++i){
        for(j=0; j<COLS; ++j) visited[i][j] = 0;
    }

    printf("No. of islands = %d\n", countIslands(map, visited, rows));


    return 0;
}

この問題のより良いロジック
も提案してください。私の解決策を改善するための提案を歓迎します。

4

5 に答える 5

9

ここでの混乱は、アルゴリズムが実際には2次時間ではなく線形時間で実行されることだと思います。

big-O表記を使用する場合、nは入力サイズを表します。ここでの入力は、ノードのグリッドであるため、単なるまたは単なるではなく、*です。あなたが質問で言ったように、あなたのアルゴリズムはで実行されます...したがって、あなたのアルゴリズムは線形時間で実行されます。rcrcO(r * c)O(n)

この問題を解決するアルゴリズムは、最悪の場合、各入力セルを1回読み取る必要があるように思われます。したがって、期待できる最高の実行時間はですO(n)。アルゴリズムが実行されるO(n)と、最悪の場合、提案したアルゴリズムよりも高速な順序で実行されるアルゴリズムを使用することはできません。

私はいくつかの巧妙なトリックを考えることができます。たとえば、*sのブロックがある場合、特定のケースでは対角線しかチェックできませんでした。つまり、あなたが持っている場合

......
.****.
.****.
.****.
.****.
......

これらのセルだけを読んでも問題ありません。

......
.*.*..
..*.*.
.*.*..
..*.*.
......

たとえば、左下隅に何かがある場合を除いて、その場合は、その左下隅を読む必要があります*。したがって、場合によっては、アルゴリズムをより高速に実行できる可能性がありますが、最悪の場合（これがO測定対象）の場合は、である必要がありますO(n)。

編集：ノードの半分しか読み取らない場合でも、ランタイムO(n/2)は同じ順序になります（O(n)）。

于 2012-08-13T14:34:10.980 に答える
2

これは、連結成分のラベル付けと密接に関連しています。接続されたコンポーネントの数は、ラベル付けの副産物にすぎません。リンクされたウィキペディアの記事で説明されているアルゴリズムは、線形時間で機能します。

于 2012-08-13T14:23:50.577 に答える
1

  1. 各アイランドノードが隣接するアイランドノードに接続する無向グラフを作成します。

  2. 未訪問のノードがありますが：

    • 未訪問のノードを選択し、深さ優先探索を実行して、訪問したすべてのノードにマークを付け、number_of_islandsを増やします。

  3. 終わり。

（1）と（2）の両方にO（n）時間がかかります。

于 2012-08-13T14:24:59.407 に答える
1

漸近的に、あなたのアプローチは最良のO（n）です。

しかし、私はいくつかのことに気づきました。

初め：

関数markVisited内で、セルの隣接セルを次の順序でチェックします。

down, right, up, left, down-right, up-left, up-right, down-left

より良い順序は次のとおりです。

left, right, up-left, up, up-right, down-left, down, down-right

これは、現在の位置のすぐ隣の値を読み取り、指定された行で順番に読み取ることから開始されるため、キャッシュでより適切に再生されます。

（対角線から始めると、より多くの場所に訪問したとマークされますが、セルが訪問されたかどうかのチェックは最後のチェックにすぎないため、時間を節約できません）。

第二に：

土地のみを含む衛星画像の最悪の場合、アルゴリズムは各セルに複数回アクセスします（セルが隣接するセルごとに1回のように）。

これは、おそらく必要とされるよりも約8倍多くのアレイアクセスを実行していることを意味します。

この問題は、データを多かれ少なかれ線形に渡すことで解決できると思います。

私は現在、アプローチを考えています。それが機能する場合は、コードを編集として追加します。

于 2012-08-14T21:10:50.180 に答える
0

島の性質についての先験的な知識がなければ、アルゴリズムを時間的にO（n）より効率的にすることはできませんが、メモリに関してはアルゴリズムを改善することができます。訪問したアレイは単に冗長です。これが簡単な試みです（ASCIIアーティメティックの使用はご容赦ください-それほど読みやすくはありませんが、コーディングはより迅速です）

#include <stdio.h>
#define COLS 12


int main()
{
    char map[][COLS] = {
            "*..........",
            "**........*",
            "...........",
            "...*.......",
            "*........*.",
            "..........*"               
            };
    int rows = sizeof(map)/sizeof(map[0]);
    int i, j;  

    int main_count = 0;

    if(map[0][0] == '*') {
        main_count++;
    }
    for(j=0; j<COLS-1; j++) {
        if((map[0][j]-map[0][j+1])==4) {
            main_count++;   
        }
    }

    for(i=1; i<rows; ++i){
        if(map[i][0] == '*' && (map[i][0]-map[i-1][0]-map[i-1][1])==-50) {
            main_count++;
        }
        for(j=0; j<COLS-1; j++) {
            if((map[i][j]-map[i][j+1])==4) {
                if( j==COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])==-50) {
                    main_count++;
                }   
                if( j!=COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])-map[i-1][j+1]==-96) {
                    main_count++;
                }   
            }
        }
    }

    printf("Number of islands: %d\n", main_count);

    return 0;
}
于 2012-08-13T20:50:19.080 に答える