[C++/アルゴリズム]白駿7576トマト:BFS


  • に関する質問:
    1.重みは同じパスで、最小日数->BFSを求める.
    2.ボックスの大きさはM*N//問題で、正しく読まず、意識フローによってN*Mを入力...時間がかかった.
  • 私が書いたコード

    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    int map[1001][1001], ch[1001][1001];
    
    int main(){
        int n, m, a, ck=0, chz = 0 ,x, y, day=0;
        // 앞, 뒤 , 오른, 왼 으로 이동하기 위한 배열
        int dx[4] = {0 , 1, 0 ,-1};
        int dy[4] = {1, 0, -1, 0};
        queue<pair<int, int>> Q;
    
        cin >> n >> m;
    
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                cin >> a;
                map[i][j] = a;
                // 익은 토마토를 모두 queue에 넣는다.
                if(a == 1) {
                    Q.push(make_pair(i, j));
                    ch[i][j] = 1;
                }
                // 이미 다 익었을 경우를 체크하기 위해 0이 하나라도 존재하는지 체크
                if(a == 0){ chz = 1;}
            }
        }
        // 0 이 존재 하지 않으면 다 익은 것으로 간주하고 0 출력
        if(chz == 0){ cout << 0; return 0;}
    
    
        while(!Q.empty()){
            x = Q.front().first;
            y = Q.front().second;
            Q.pop();
    
            for(int i=0; i<4; i++){
                if(x+dx[i] < 0 || x+dx[i] >= m || y+dy[i]<0 || y+dy[i] >= n) continue;
                
                // 토마토가 익지 않았으며, 이미 지나오지 않은 경우
                if(ch[x+dx[i]][y+dy[i]] == 0 && map[x+dx[i]][y+dy[i]] == 0){
                
                    Q.push(make_pair(x+dx[i], y+dy[i]));
                    // 인접한 익은 토마토의 일수 + 1
                    ch[x+dx[i]][y+dy[i]] = ch[x][y] + 1;
                    map[x+dx[i]][y+dy[i]] = 1;
                }
            }
        }
        // 여기까지 토마토가 익을 경우 최대 날짜.
    
        // map 에 대해 포문돌면서 0 이 있으면(토마토 모두 다 익지 않은 경우) -1 출력
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == 0 ){ cout << -1; return 0;}
            }
        }
        // 그렇지 않으면 마지막으로 토마토가 익은 날짜에서 원래 익었던 토마토를 하루 센것을 제외해야 하므로 -1하여 출력
        cout << ch[x][y] -1 << endl;
        return 0;
    }