[BOJ/C+]7576号トマト

14981 ワード
boj cpp テキストリンク
この問題はBFSアルゴリズムを用いて解決した.DFS & BFS
  • 従来のBFSはアクセス処理を行っていたが,今回の問題では直接グラフィックに値を付け,その中で最大の値を時間として求める.
  • のグラフィック座標の移動をdx,dy配列として実現する.
  • BFSでグラフィック全体をブラウズして値を更新した後、グラフィックに0がある場合は-1を出力します.

    • Code

    #include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 1001
using namespace std;

int m,n, k;
int result=0;
int graph[MAX][MAX];
queue<pair<int, int>> tomato;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool success=true;

void Input(){
    cin>>m>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>graph[i][j];
            if(graph[i][j]==1){
                tomato.push(make_pair(i, j));
            }
        }
    }
}

void BFS(){
    while(!tomato.empty()){
        int y=tomato.front().first;
        int x=tomato.front().second;
        tomato.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)&&graph[ny][nx]==0){
                graph[ny][nx]=graph[y][x]+1;
                tomato.push(make_pair(ny, nx));
            }
        }
    }
}

int Solution(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(graph[i][j]==0){
                success=false;
            }
            if(result<graph[i][j]){
                result=graph[i][j];
            }
        }
    }
    if(!success)
        return -1;
    else
        return result-1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    BFS();
    cout<<Solution()<<endl;
    return 0;
}
    linux環境で静的ライブラリ、動的ライブラリコンパイラを同時に使用
    TIL 20210928[航海9913日]