Untitled
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; }