254D - Rats - CodeForces Solution

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

#define point pair<int, int>

const int N = 2000, M = 2000;
int n, m, d;

vector<vector<char>> matrix(N, vector<char>(M));
vector<point> rats;
set<point> killed_rats;


bool check_incorrect_point(point p) {
    if (not (0 <= p.first && p.first < n))
        return true;
    if (not (0 <= p.second && p.second < m))
        return true;
    return matrix[p.first][p.second] == 'X';
}

bool not_in_visited(const vector<point>& visited, point dot) {
    return find(visited.begin(), visited.end(), dot) == visited.end();
}


void update_next(vector<pair<point, int>>& next, const vector<point>& visited, int val, point dot) {
    if (0 <= dot.first + 1 < n && matrix[dot.first + 1][dot.second] != 'X')
        if (not_in_visited(visited, {dot.first + 1, dot.second}))
            next.emplace_back(point {dot.first + 1, dot.second}, val);

    if (0 <= dot.first - 1 < n && matrix[dot.first - 1][dot.second] != 'X')
        if (not_in_visited(visited, {dot.first - 1, dot.second}))
            next.emplace_back(point {dot.first - 1, dot.second}, val);

    if (0 <= dot.second + 1 < m && matrix[dot.first][dot.second + 1] != 'X')
        if (not_in_visited(visited, {dot.first, dot.second + 1}))
            next.emplace_back(point {dot.first, dot.second + 1}, val);

    if (0 <= dot.second - 1 < m && matrix[dot.first][dot.second - 1] != 'X')
        if (not_in_visited(visited, {dot.first, dot.second - 1}))
            next.emplace_back(point {dot.first, dot.second - 1}, val);
}

vector<point> BFS(point start, bool count_hit=true) {
    vector<pair<point, int>> next = {{start, 0}};
    vector<point> visited;

    while (!next.empty()) {
        pair<point, int> last = next[0];
        point current = last.first;
        next.erase(next.begin());
        visited.emplace_back(current);

        if (matrix[current.first][current.second] == 'R' && count_hit)
            killed_rats.emplace(current);

        int val = last.second + 1;
        if (val <= d)
            update_next(next, visited, val, current);
    }
    return visited;
}

vector<point> find_survived() {
    vector<point> survived;
    for (auto rat: rats)
        if (killed_rats.find(rat) == killed_rats.end())
            survived.emplace_back(rat);
    return survived;
}

set<point> intersection(set<point> a, set<point> b) {
    set<point > intersect;
    set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                     inserter(intersect, intersect.begin()));
    return intersect;
}

set<point> from_vec_to_set(vector<point> a) {
    set<point> result;
    for (auto el: a)
        result.insert(el);
    return result;
}

int main() {
#ifdef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> d;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
            if (matrix[i][j] == 'R')
                rats.emplace_back(i, j);
        }
    }
    // --

    if (rats.size() > (d*2*d+2*d+1) * 2) {
        cout << -1;
        return 0;
    }

    map<point, set<point>> precount_BFS;

    pair<point, point> result;
    bool break_ = false;
    bool first_else = true;

    point start_rat = rats[0];
    vector<point> start_rat_grenade = BFS(start_rat, false);
    for (auto dot1: start_rat_grenade) {
        killed_rats = {start_rat};
        BFS(dot1);
        if (killed_rats.size() == rats.size()) {
            break_ = true;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (matrix[i][j] != 'X' && point{i, j} != dot1)
                        result = {dot1, point{i, j}};
        } else {
            if (rats.size() - killed_rats.size() <= d * 2 * d + 2 * d + 1) {
                if (first_else) {
                    first_else = false;
                    for (auto rat: rats)
                        precount_BFS[rat] = from_vec_to_set(BFS(rat, false));
                }
                vector<point > survived = find_survived();
                set<point > second_grenade = precount_BFS[survived[0]];
                bool flag = true;
                for (auto rat: survived) {
                    set<point > current_rat = precount_BFS[rat];
                    second_grenade = intersection(second_grenade, current_rat);
                    if (second_grenade.empty()) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    break_ = true;
                    result = {dot1, *second_grenade.begin()};
                }
            }
        }

        if (break_)
            break;
    }

    if (result == pair {point {0, 0}, point {0, 0}})
        cout << - 1;
    else
        cout << result.first.first + 1 << ' ' << result.first.second + 1
             << ' ' << result.second.first + 1 << ' ' << result.second.second + 1;
}