💉質問内容

問題に答える

💉にゅうしゅつりょく

🧺入力
画像サイズを表すmとn、および画像を表すmを入力する× nサイズの2次元配列図を与えます.制限条件は以下の通りです.
* 1 <= m, n <= 100
*画像の要素は0以上2^31-1以下の任意の値です.
*画像の要素値が0の場合は、シェーディングされていない領域を示します.
🧺しゅつりょく
戻りタイプは、2つの要素の整数配列です.図の領域の数と最大の領域の数を返します.

🔋サンプルI/O

🔮入力例

🔮サンプル出力

💉もんだいぶんせき

🔋ぶんかつ

bfs,dfs,グラフィック理論,brootfors

🔋難易度

(解決済み.ac規格)銀I~金IV

💉問題を解く

🔋解法

個人的にはbfsで解決しました
これは非常に簡単な問題です.
これはただのbfs問題で、説明することはありません.
Brootforceを使用して、すべてのポイントを巡回します.このポイントがアクセスされていないポイントですが、0ではない場合は、bfsを実行します.

🔋ソースコード

#include <vector>
#include <utility>
#include <queue>

constexpr int MAX = 101;

std::vector<int> solution(int m, int n, std::vector<std::vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;

    const int dx[4] = { 0, 0, 1, -1 };
    const int dy[4] = { 1, -1, 0, 0 };

    bool visit[MAX][MAX] = { false, };

    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(!visit[i][j] && picture[i][j] != 0) {
                ++number_of_area;
                std::queue<std::pair<int, int>> q;
                q.push({ i, j });
                visit[i][j] = true;
                int result = 1;

                while(!q.empty()){
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();

                    for(int i=0;i<4;++i){
                        int ny = y + dy[i];
                        int nx = x + dx[i];

                        if(ny >= 0 && nx >= 0 && ny < n && nx < m){
                            if(!visit[ny][nx] && picture[ny][nx] == picture[y][x]){
                                visit[ny][nx] = true;
                                q.push({ ny, nx });
                                ++result;
                            }
                        }
                    }
                }
                max_size_of_one_area = std::max(result, max_size_of_one_area);
            }
        }
    }t

    std::vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

まず、プログラマーのところで問題を解くのは初めてなので、慣れません.
簡単な問題ではあるがI/O例が煩わしいため紛らわしい.
I/Oの例は、既存のc++std::vector>の1次元および2次元の位置とは逆です.怒った.
元のc++std::vector>に置き換えるには、次の手順に従います.
{{1, 1, 1, 0, 0, 0}, {1, 2, 0, 0, 0, 0}, {1, 2, 0, 0, 0, 0}, {0, 0, 1, 1, 3, 3}}
これは正しいです.
{{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}}
これを使ってくれて、怒っています.
このコードはとっくに5~7分で作成されているので、30分もうろうろしていました.
mは6、nは4だと思っていたので、nはx座標の最値、mはy座標の最値です.ああ...
逆にすればいいのに...1発の詩.
個人的に見ると、問題は白俊がもっと柔軟で、可読性がもっと良いことだ.

💉終了時..。

気になる部分があればコメントで質問しましょう~