General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
129032768 Practice:
Czhgugugu
254D - 41 C++17 (GCC 9-64) Accepted 187 ms 20680 KB 2021-09-17 05:56:08 2021-09-17 05:56:08
→ Source
//  ddd
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;

#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif

const int N = 1005;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const ll P = 998244353LL;

int n, m, d;
char s[N][N];
bool vis[N][N], cov[N][N];
vector <pin> pos1, pos2, rat, covPot;

struct Node {
    int x, y, curd;
};
queue <Node> q;

inline bool valid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m; 
}

inline void getPos1(int sx, int sy) {
    pos1.clear();
    q.push((Node) {sx, sy, d});
    vis[sx][sy] = 1;
    vector <pin> pot;
    for (; !q.empty(); ) {
        int x = q.front().x, y = q.front().y, cur = q.front().curd;
        q.pop();
        pot.emplace_back(pin(x, y));
        if (cur == 0) continue;
        --cur;
        for (int i = 0; i < 4; i++) {
            int tox = x + dx[i], toy = y + dy[i];
            if (!valid(tox, toy)) continue;
            if (vis[tox][toy]) continue;
            if (s[tox][toy] == 'X') continue;
            vis[tox][toy] = 1;
            q.push((Node) {tox, toy, cur});
        }
    }
    for (int i = 0; i < pot.size(); i++) {
        int x = pot[i].first, y = pot[i].second;
        vis[x][y] = 0;
        if (s[x][y] != 'X') pos1.emplace_back(pin(x, y));
    }
}

inline void getPos2(int sx, int sy) {
    pos2.clear();
    q.push((Node) {sx, sy, d});
    vis[sx][sy] = 1;
    vector <pin> pot;
    for (; !q.empty(); ) {
        int x = q.front().x, y = q.front().y, cur = q.front().curd;
        q.pop();
        pot.emplace_back(pin(x, y));
        if (cur == 0) continue;
        --cur;
        for (int i = 0; i < 4; i++) {
            int tox = x + dx[i], toy = y + dy[i];
            if (!valid(tox, toy)) continue;
            if (vis[tox][toy]) continue;
            if (s[tox][toy] == 'X') continue;
            vis[tox][toy] = 1;
            q.push((Node) {tox, toy, cur});
        }
    }
    for (int i = 0; i < pot.size(); i++) {
        int x = pot[i].first, y = pot[i].second;
        vis[x][y] = 0;
        if (s[x][y] != 'X') pos2.emplace_back(pin(x, y));
    }
}

inline void cover(int sx, int sy) {
    q.push((Node) {sx, sy, d});
    vis[sx][sy] = 1;
    vector <pin> pot;
    for (; !q.empty(); ) {
        int x = q.front().x, y = q.front().y, cur = q.front().curd;
        q.pop();
        pot.emplace_back(pin(x, y));
        if (cur == 0) continue;
        --cur;
        for (int i = 0; i < 4; i++) {
            int tox = x + dx[i], toy = y + dy[i];
            if (!valid(tox, toy)) continue;
            if (vis[tox][toy]) continue;
            if (s[tox][toy] == 'X') continue;
            vis[tox][toy] = 1;
            q.push((Node) {tox, toy, cur});
        }
    }
    for (int i = 0; i < pot.size(); i++) {
        int x = pot[i].first, y = pot[i].second;
        vis[x][y] = 0;
        cov[x][y] = 1;
        covPot.emplace_back(pin(x, y));
    }
}

inline void clear() {
    for (int i = 0; i < covPot.size(); i++) {
        int x = covPot[i].first, y = covPot[i].second;
        cov[x][y] = 0;
    }
    covPot.clear();
}

inline bool chk() {
    for (int i = 0; i < rat.size(); i++) {
        int x = rat[i].first, y = rat[i].second;
        if (!cov[x][y]) return 0;
    }
    return 1;
}

#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif

int main() {
#ifndef ONLINE_JUDGE
    freopen("sample.in", "r", stdin);
    clock_t st_clock = clock();
#endif

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == 'R') {
                rat.emplace_back(pin(i, j));
            }
        }
    assert(rat.size() != 0);
    getPos1(rat[0].first, rat[0].second);
    if (pos1.empty()) {
        puts("-1");
        return 0;
    }
    bool flag = 0;
    for (int i = 0; i < pos1.size(); i++) {
        int x = pos1[i].first, y = pos1[i].second;
        cover(x, y);
        int px = 0, py = 0;;
        for (int j = rat.size() - 1; j >= 0; j--) {
            if (cov[rat[j].first][rat[j].second]) continue;
            px = rat[j].first, py = rat[j].second;
            break;
        }
        clear();
        if (px == 0 && py == 0) {
            flag = 1;
            int ans2x, ans2y;
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= m; k++) {
                    if (j == x && k == y) continue;
                    if (s[j][k] != '.') continue;
                    ans2x = j, ans2y = k;
                    break;
                }
            printf("%d %d %d %d\n", x, y, ans2x, ans2y);
            break;
        } else {
            getPos2(px, py);
            if (pos2.empty()) {
                puts("-1");
                flag = 1;
                break;
            }
            for (int j = 0; j < pos2.size(); j++) {
                int x2 = pos2[j].first, y2 = pos2[j].second;
                if (x2 == x && y2 == y) continue;
                cover(x, y);
                cover(x2, y2);
                if (chk()) {
                    flag = 1;
                    printf("%d %d %d %d\n", x, y, x2, y2);
                    break;
                }
                clear();
            }
            if (flag) break;
        }
    }
    if (!flag) puts("-1");

#ifndef ONLINE_JUDGE
    clock_t ed_clock = clock();
    printf("time = %f ms\n", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
    printf("memory = %.2f MB\n", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details