Untitled

mail@pastecode.io avatar
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;
}