Round A two 2019 – Kick Start 2019

#include <bits/stdc++.h>

using namespace std;
const int N = 100000, INF = 0x3f3f3f3f;
char grid[N][N];
int dist[N][N];
int directions[4][2] = {{0,  1},
                        {0,  -1},
                        {1,  0},
                        {-1, 0}};
int T, r, c;

bool is_valid(int mid, int r, int c) {
    queue<pair<int, int>> queue;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            dist[i][j] = -1;
            if (grid[i][j] == '1') {
                queue.push(make_pair(i, j));
                dist[i][j] = 0;
            }
        }
    }
    while (!queue.empty()) {
        pair<int, int> cur = queue.front();
        for (auto &direction:directions) {
            int x = cur.first + direction[0];
            int y = cur.second + direction[1];
            if (x >= 0 && x < r && y >= 0 && y < c && dist[x][y] == -1) {
                dist[x][y] = dist[cur.first][cur.second] + 1;
                queue.push(make_pair(x, y));
            }
        }
    }
    int max_sum = INT_MIN;
    int min_sum = INT_MAX;
    int max_sub = INT_MIN;
    int min_sub = INT_MAX;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (dist[i][j] > mid) {
                max_sum = max(max_sum, i + j);
                min_sum = min(min_sum, i + j);
                max_sub = max(max_sub, i - j);
                min_sub = min(min_sub, i - j);
            }
        }
    }
    if (min_sub == INT_MAX)
        return true;

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (abs(max_sum - (i + j) <= mid && abs(min_sum - (i + j)) <= mid) && abs(max_sub - (i - j)) &&
                abs(min_sub - (i - j)) <= mid) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> T;
    int index = 1;
    while (T-- > 0) {
        cin >> r >> c;
        for (int i = 0; i < r; ++i) {
            cin >> grid[i];
        }
        int low = 0;
        int high = r + c;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (is_valid(mid, r, c))
                high = mid;
            else
                low = mid + 1;
        }
        cout << "Case #" << index << ": " << low << endl;
    }
    return 0;
}

 

0