# Untitled

user_1944374
c_cpp
2 years ago
1.8 kB
8
Indexable
Never
```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

template <typename T>
class Queue {
int start, end;
vector<T> v;
public:
Queue() {
start = 0;
end = 0;
}
void push(T e) {
v.push_back(e);
end++;
}
bool empty() {
return start == end;
}
T front() {
return v[start];
}
void pop() {
start++;
}
int size() {
return end - start;
}
};

class Pair {
public:
int F, S;
};

int main() {
int m, n, minute = 0; cin >> m >> n;
int grid[m][n];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
Queue<Pair> q;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
cin >> grid[i][j];
if(grid[i][j] == 2) {
q.push({i, j});
}
}
}
q.push({-1, -1});

while(!q.empty()) {
Pair p = q.front(); q.pop();
if (p.F == -1 && p.S == -1) {
if(q.size() >= 1) {
minute++;
q.push({-1, -1});
continue;
}
else break;
}
for(int i = 0; i < 4; i++) {
int x = p.F + dx[i], y = p.S + dy[i];
if(x < 0 || x >= m || y < 0 || y >= n) continue;
if(grid[x][y] == 2 || grid[x][y] == 0) continue;
grid[x][y] = 2;
q.push({x, y});
}
}

for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
minute = -1;
break;
}
}
}
cout << minute << "\n";
return 0;
}```