[アルゴリズム]BOJ 2573(氷山)

ソース:https://www.acmicpc.net/problem/2573

質問する

地球温暖化で北極氷山が溶けている.図1に示すように、氷山を2次元アレイに表示します.氷山の各部分の高さ情報は,配列された各セルに正の整数として格納される.氷山以外の海に対応する格には0が格納されている.図1では、スペースはすべてゼロで埋め込まれていると思います.

図1.行数5、列数7の2 Dアレイの氷山の高さ情報を格納します.
氷山の高さは海水との接触が多い場所でより速く減少するため、配列中の氷山の各部分に対応する格子の高さは毎年、格子の中で東西南北4方向に付着する0の格子の個数を減少させる.ただし、各セルに格納される高さは0より小さくなりません.海水は湖水のように氷山に囲まれているかもしれない.従って、図1の氷山は、図2に示すように1年後に変形する.
図3は、図1の氷山の2年後の変化を示す.2 D配列では,東西南北方向の格子が互いに接続されている.したがって、図2の氷山は1つであり、図3の氷山は3つに分かれている.

氷山が1つ与えられた場合、プログラムを作成して、この氷山が2つ以上分離された最初の時間(年)を求めます.図1の氷山について、答えは2です.全てが溶けるまで2つ以上離さないと、プログラムは0を出力します.

入力

1行目では、2つの整数NとMは、2次元配列の行数と列数を表すスペースで区切られます.NとMは3以上300以下である.次のN行では、各行の間にスペースがあり、M個の整数は配列の各行を表します.各グリッドの値は0以上10以下です.配列では、氷山が占める格の個数、すなわち1以上の整数が占める格の個数が10000以下である.配列の最初の行と最後の行と最後の列は常に0で埋め込まれます.

しゅつりょく

1行目は氷山分離の最初の時間(年)を出力する.氷山が溶けるまで分離していない場合は0を出力します.

正しいコード

#include<bits/stdc++.h>
#define endl '\n'

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

using namespace std;

int m,n;

bool bfs(vector<vector<int>>& v,vector<vector<bool>>& c, int y, int x)
{
    if(y>=m || x>=n || y<0 || x<0) return false;
    if(c[y][x]) return false;

    c[y][x]=true;
    return true;
}

int main()
{
    pair<int,int> pos;

    cin >> m >> n;

    vector<vector<int>> v(m,vector<int> (n,0));
    vector<vector<bool>> c(m,vector<bool> (n,0));
    vector<vector<int>> czero(m,vector<int> (n,0));

    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> v[i][j];
        }
    }

    queue<pair<int,int>> q;

    int cnt = -1;

    bool check = true;

    while(check)
    {
        cnt++;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                czero[i][j]=0;
                if(v[i][j]>0)
                {
                    pos.first = i;
                    pos.second = j;
                    check = false;
                }
                else c[i][j]=true;
            }
        }

        if(check)  break;

        q.push({pos.first,pos.second});

        while(!q.empty())
        {
            for(int i=0; i<4; i++)
            {
                if(bfs(v, c , q.front().first+dy[i], q.front().second+dx[i]))
                {
                    q.push({q.front().first+dy[i],q.front().second+dx[i]});
                }
            }
            q.pop();
        }

        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(!c[i][j])
                {
                    cout << cnt << endl;
                    return 0;
                }
                c[i][j]=false;
                if(v[i][j]>0)
                {
                    for(int k=0; k<4; k++)
                    {
                        if(v[i+dy[k]][j+dx[k]]<=0)  czero[i][j]++;
                    }
                }
            }
        }
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(czero[i][j]>0)
                v[i][j]-=czero[i][j];
            }
        }
        check = true;
    }

    cout << 0 << endl;

    return 0;
}

解答と思考過程

すぐに問題を解決したいだけで、多くの間違いを犯した.

問題がうまく読めず、条件

を漏らした.
乱編

コードのため、モジュール化は行われていない.

この2つの理由で、デバッグに時間がかかりました.popは行われていなかったため、無限循環になり、氷山周辺の水の量を把握していないため、より速く減少したため、ミスが発生した.
私の今の段階では、問題を素早く解くよりも、よく見る習慣を身につけなければなりません.