[伯俊]2012号有機白菜

質問リンク:https://www.acmicpc.net/problem/1012

質問する

次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.
(1つの白菜の上下左右4方向にもう1つの白菜がある場合は隣接とみなす)
ハンナが白菜を植える畑は平らではなく,白菜を植える場所はみなそろっている.白菜が集まっているところに白菜のミミズが1匹あればいいので、隣接する白菜がいくつか分布しているかを調べてみると、全部で何匹必要かがわかります.
例えば、白菜畑が以下のように構成されている場合、白菜ミミズは少なくとも5匹必要である.
(0は白菜を植えていない土地を表し、1は白菜を植えた土地を表す.)

入力

入力された第1行は、試験例の個数Tを与える.次の行から、各試験例について、第1行は、キャベツ栽培地の横長M(1≦M≦50)および縦長N(1≦N≦50)およびキャベツ栽培場所の個数K(1≦K≦2500)を与えた.次いでK行はハクサイの位置X(0≦X≦M−1),Y(0≦Y≦N−1)を与える.

しゅつりょく

各試験箱について、所望の最小白菜白ミミズ数を出力する.

問題を理解する

白菜を植える畑に関する情報を提供する.白菜を植えるところは1で、違うところは0です.問題を簡単に考えて、白菜の隣のところを別の小田と考えれば、この大地で何人かの小田を探すことだ.

質問へのアクセス

受信入力

入力に従って、畑の白菜の位置をチェックします.

地を最初から数えて、白菜のあるところを検索します.

searchを行った場合、上下左右をチェックし、白菜の場所があればその部分を再検索します.検索前に検索したので、その部分は0に変わります.

検索終了後、小さなブロックが見つかったのでcount+1.

一つのtestcaseが終了した後、他のtestcaseの入力を受信し、3-5を行う.

コード実装（C++）

#include <iostream>
#include <vector>

using namespace std;

bool farm[50][50] ={false,};
int W, H, cabbageNum;
int testcase;
int checkNum;
int wCheck[4] = {-1,0,0,1};
int hCheck[4] = {0,-1,1,0};

void search(int h, int w){
    int nextW, nextH;
    for(int i = 0 ; i < 4 ; i++){
        nextW = w + wCheck[i]; nextH = h + hCheck[i];
        if(nextW >= 0 && nextH >= 0 && nextW < W && nextH < H && farm[nextH][nextW]){
            farm[nextH][nextW] = false;
            search(nextH, nextW);
        }
    }
}
int dfs(){
    int cnt = 0;
    for(int i = 0 ; i < H ; i++){
        for(int j = 0 ; j < W ; j++){
            if(farm[i][j]){
                cnt++;
                farm[i][j] = false;
                search(i, j);
            }
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> testcase;
    int w, h;
    for(int i = 0 ; i < testcase ; i++){
        cin >> W >> H >> cabbageNum;
        for(int i = 0 ; i < cabbageNum ; i++){
            cin >> w >> h;
            farm[h][w] = true;
        }
        cout << dfs() << "\n";
    }

}

評価

これは簡単な問題だ.しかし,注意が足りなかったため,一部を除いて実施し,誤り箇所の検索にかなりの時間を費やした.これからはすべてを考えて、書いて、コードを始めます.