Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.8 kB
1
Indexable
Never
//Please do not modify the header files.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

class Queue{
public:
    int size;
    vector<vector<int>> v;
    
    Queue(){
        size = 0;
    }
    
    void Enqueue(int m,int n){
        vector<int> temp;
        temp.push_back(m);
        temp.push_back(n);
        v.push_back(temp);
        size++;
    }
    
    void Dequeue(){
        if(v.size()!=0){
            v.erase(v.begin());
            size--;
        }
    }
    
    vector<int> Front(){
        if(size!=0){
            return v[0];
        }
        vector<int> temp{-1,-1};
        return temp;   
    }
    
    int length(){
        return size;
    }
};


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int m;//downwards
    int n;
    int temp;
    int unvac=0;
    Queue q;
    vector<vector<int>> col;
    vector<int> row;
    cin>>m;
    cin>>n;
    for(int i = 0; i<m;i++){
        for(int j =0 ; j<n;j++){
            cin>>temp;
            row.push_back(temp);
            if(temp == 2){
                q.Enqueue(i, j);
            }
            else if (temp==1){
                unvac++;
            }
        }
        col.push_back(row);
        row.clear();
        //cout<<"pushed back"<<endl;
    }
    int time = 0;
    while(q.length()!=0){
        time++;
        int s = q.length();
        for(int temp = 0; temp<s;temp++){
            vector<int> pos;
            pos = q.Front();
            int mpos = pos[0];
            int npos = pos[1];
            //cout<<"pos is m "<<mpos<<" n "<<npos<<" val at this "<<col[mpos][npos]<<endl;
            if(npos>=1){
                if(col[mpos][npos-1]==1){
                    col[mpos][npos-1]=2;
                    unvac--;
                    q.Enqueue(mpos,npos-1);
                }
            }
            if(npos<=n-2){
                if(col[mpos][npos+1]==1){
                    col[mpos][npos+1]=2;
                    unvac--;
                    q.Enqueue(mpos,npos+1);
                }
            }
            if(mpos>=1){
                if(col[mpos-1][npos]==1){
                    col[mpos-1][npos]=2;
                    unvac--;
                    q.Enqueue(mpos-1,npos);
                }
            }
            if(mpos<=m-2){
                if(col[mpos+1][npos]==1){
                    col[mpos+1][npos]=2;
                    unvac--;
                    q.Enqueue(mpos+1,npos);
                }
            }
            q.Dequeue();
        }
    }
    
    if(unvac== 0){
        cout<<time-1;
    }
    else{
        cout<<-1;
    }
    
    //cout<<col[2][0];//down right
    
    
    
    return 0;
}