Untitled
unknown
c_cpp
2 years ago
2.0 kB
1
Indexable
Never
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <climits> using namespace std; class Queue { int start, end; vector<int> v; public: Queue() { start = 0; end = 0; } void push(int e) { v.push_back(e); end++; } bool empty() { return start == end; } int front() { return v[start]; } void pop() { start++; } int size() { return end - start; } }; int main() { int m, n; cin >> m >> n; int grid[m][n]; minute = 0; Queue<int> qx; Queue<int> qy; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { cin >> grid[i][j]; if(grid[i][j] == 2) { qx.push(i); qy.push(j); } } } qx.push(-100); qy.push(-100); int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; while(!q.empty()) { auto F, S = qx.front(), qy.front(); qx.pop(); qy.pop(); if (F == -100 && S == -100) { if(qx.size() >= 1) { minute++; qx.push(-100); qy.push(-100); continue; } else break; } for(int i = 0; i < 4; i++) { int x = F + dx[i], y = 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; qx.push(x); qy.push(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; }