[アルゴリズム解答解析]プログラマーデジタルカメラカラーブック(2017 KACOコード予選)

先週の木曜日から月曜日まで、5日間、寝るソフト+コット準備+ココア、あなたのネットコット+ワクチン接種嵐のような5日間を過ごしました.今日の午後はよく遊んで、よく休んでいました.
また走る前に、今日は簡単な問題をしました.
基本的な問題なのでc++・swiftあなたのサイトディレクトリの検索、IDEは無効になり、c++さえオプションに含まれていません.私は結局swiftで解くことにしましたが、2日前から急いでswiftの使用に慣れていましたが、確かに慣れていないので、時間がかかりました.3つのうち2本しかありません.これも欲張りで、、ほほほ
今日からswiftも同時に練習するつもりです.
できればIDEは使いません!
だから今日の質問はプログラマ!

プログラマ

ココア友彩本
出版社の編集者オフィチトニオは、絵本に描かれた円を何枚も描いた.複数の画像を難易度順にカラー絵本に入れたい魚は、領域が多ければ塗りにくくなることを発見し、画像の難易度を領域数と定義した.(領域とは上下左右に接続された同じ色の空間を指す.)
図にどれだけの領域があるか、最大の領域の幅がどれだけあるかを計算するプログラムを作成します.

上図には12の領域があり、最も広い領域は魚の皮魚の顔で、幅は120です.

にゅうしゅつりょく

画像サイズを表すmとn、および画像を表すmを入力する× nサイズの2次元配列図を与えます.制限条件は以下の通りです.

1 <= m, n <= 100

pictureの要素は0以上2^31-1以下の任意の値である.

pictureでの元素値がゼロの場合、色がつかない領域を表す.

戻りタイプは、2つの要素の整数配列です.図の領域の数と最大の領域の数を返します.
mnpictureanswer64[[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]][4, 5]

私の答え

これは簡単なBFS/DFS質問です.
再帰的実装を利用してBFSを選択した.
塗りと未アクセスのセルが見つかるたびに、領域数が増加し、同じ色の領域が再帰的に検索されます.パラメータによってスキップされた領域サイズ変数を上げ、1つの領域の検索が完了した後、最大領域幅と比較して更新します.swift中説call by reference使い方、使えるinout.これはswiftにおいて自然な方法であるかどうかのさらなる理解が必要である.

コード#コード#

cpp

#include <vector>

using namespace std;

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

int M;
int N;
vector<vector<int>> map;

void bfs(vector<vector<bool>> & visited, int r, int c, int & size, int color){

    for(int i=0; i<4; i++){
        int nr = r + dy[i];
        int nc = c + dx[i];

        if(nr>=0 && nr<M && nc>=0 && nc<N && map[nr][nc] == color && !visited[nr][nc]){
            visited[nr][nc] = true;
            size++;
            bfs(visited, nr, nc, size, color);
        }
    }

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

    map = picture;
    vector<vector<bool>> visited(m, vector<bool>(n, false));

    M = m;
    N = n;

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(picture[i][j] > 0 && !visited[i][j]){
                number_of_area++;
                visited[i][j] = true;
                int size = 1;
                bfs(visited, i, j, size, picture[i][j]);
                if(max_size_of_one_area < size) max_size_of_one_area = size;
            }
        }
    }

    vector<int> answer = {number_of_area, max_size_of_one_area};
    return answer;
}

swift

import Foundation

var M = 0
var N = 0
var map = [[Int]]()

let dy = [-1,0,1,0]
let dx = [0,1,0,-1]

func bfs(visited : inout [[Bool]], r : Int, c : Int, size : inout Int, color : Int ) -> Void {
    for i in 0..<4 {
        let nr = r + dy[i]
        let nc = c + dx[i]
        
        if nr>=0 && nr<M && nc>=0 && nc<N && !visited[nr][nc] && map[nr][nc]==color {
            visited[nr][nc] = true
            size += 1
            bfs(visited: &visited, r: nr, c: nc, size: &size, color: color)
        }
    }
}

func solution(_ m : Int, _ n : Int, _ picture : [[Int]]) -> [Int]{
    var number_of_area = 0
    var max_size_of_one_area = 0
    let row = [Bool](repeating: false, count: n)
    var visited = [[Bool]](repeating: row, count:m)
    
    map = picture
    M = m
    N = n
    
    for i in 0..<m {
        for j in 0..<n {
            if picture[i][j]>0 && !visited[i][j] {
                number_of_area += 1
                visited[i][j] = true
                var size = 1
                bfs(visited: &visited, r: i, c: j, size: &size, color: picture[i][j])
                if max_size_of_one_area < size {
                    max_size_of_one_area = size
                }
            }
        }
    }
    
    return [number_of_area, max_size_of_one_area]
}