QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80008#2924. Lone RookperspectiveAC ✓2649ms11948kbC++234.8kb2023-02-21 16:49:512023-02-21 16:50:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-21 16:50:00]
  • 评测
  • 测评结果:AC
  • 用时:2649ms
  • 内存:11948kb
  • [2023-02-21 16:49:51]
  • 提交

answer

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define INP "input"
#define OUT "output"

/* some template */
template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& a) {
    out << (int)a.size() << '\n';
    for (const auto& v : a) out << v << ' ';
    out << endl;
    return out;
}

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<vector<T> >& a) {
    out << (int)a.size() << '\n';
    for (const auto& v : a) {
        for (const auto& value : v) out << value << ' ';
        out << endl;
    }
    return out;
}

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}
/* end template */

const long long INF_LL = 1e18;
const int INF = 1e9 + 100;
const long double EPS = 1e-6;
const int BLOCK = 550;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

void open_file() {
#ifdef THEMIS
    freopen(INP ".txt", "r", stdin);
    freopen(OUT ".txt", "w", stdout);
#endif  // THEMIS
}

const int maxN = 1e6 + 100;
const int MOD = 1e9 + 7;

void sol() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    cin >> s;

    queue<pair<int, int> > Q;
    vector<vector<int> > attack(n, vector<int>(m, 0));
    vector<vector<int> > visited(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'R') {
                Q.push({i, j});
                visited[i][j] = 1;
            }
            if (s[i][j] == 'K') {
                for (int dx : {-1, 1, -2, 2}) {
                    for (int dy : {abs(dx) - 3, 3 - abs(dx)}) {
                        int x = i + dx;
                        int y = j + dy;
                        if (x >= 0 && x < n && y >= 0 && y < m) {
                            attack[x][y] += 1;
                        }
                    }
                }
            }
        }
    }

    while ((int)Q.size() != 0) {
        auto it = Q.front();
        Q.pop();
        int i = it.first, j = it.second;
        if (s[i][j] == 'T') {
            cout << "yes";
            return;
        }

        if (s[i][j] == 'K') {
            for (int ddx : {-1, 1, -2, 2}) {
                for (int ddy : {abs(ddx) - 3, 3 - abs(ddx)}) {
                    int x = i + ddx;
                    int y = j + ddy;
                    if (x >= 0 && x < n && y >= 0 && y < m && --attack[x][y] == 0) {
                        for (int h = 0; h < 4 && visited[x][y] == 0; h++) {
                            for (int k = 1; k <= max(n, m); k++) {
                                int u = x + dx[h] * k;
                                int v = y + dy[h] * k;
                                if (u >= 0 && u < n && v >= 0 && v < m) {
                                    if (visited[u][v] == 1) {
                                        visited[x][y] = 1;
                                        Q.push({x, y});
                                        break;
                                    }
                                    if (s[u][v] == 'K' && visited[u][v] == 0) {
                                        break;
                                    } 
                                } else {
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int h = 0; h < 4; h++) {
            for (int k = 1; k <= max(n, m); k++) {
                int u = i + dx[h] * k;
                int v = j + dy[h] * k;
                if (u >= 0 && u < n && v >= 0 && v < m) {
                    if (visited[u][v] == 0 && attack[u][v] == 0) {
                        visited[u][v] = 1;
                        Q.push({u, v});
                    }
                    if (s[u][v] == 'K' && visited[u][v] == 0) {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
    }
    cout << "no";
}

void solve() {
    clock_t start, end;
    start = clock();
    int T = 1;
    // cin >> T;
    int TestCase = 0;
    while (T--) {
        TestCase += 1;
        cerr << "Processing test = " << TestCase << '\n';
        // cout << "Case #" << TestCase << ": ";
        sol();
        // if (T) cout << '\n';
    }
    end = clock();
    cerr << "Time = " << (double)(end - start) / (double)CLOCKS_PER_SEC << '\n';
}

int main(int argc, char* argv[]) {
    // srand(time(nullptr));
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    open_file();
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3692kb

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

5 3
KKT
.K.
K..
...
KKR

output:

yes

result:

ok single line: 'yes'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3664kb

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

2 5
RKKK.
...KT

output:

no

result:

ok single line: 'no'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

5 6
.....T
..K...
..KK..
...K..
R.....

output:

no

result:

ok single line: 'no'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

3 4
...K
T.KR
..K.

output:

no

result:

ok single line: 'no'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3712kb

input:

6 3
.R.
...
...
KKK
.K.
.T.

output:

yes

result:

ok single line: 'yes'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3684kb

input:

6 6
..K..T
..K...
......
..KK.K
...K..
R.....

output:

no

result:

ok single line: 'no'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

6 6
..K...
..KTK.
......
..KK..
...K..
R.....

output:

yes

result:

ok single line: 'yes'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

14 6
T.K..K
......
K....K
KKK.KK
KKK.KK
......
......
..K.KK
.K...K
......
..KK.K
...K..
......
R.K.K.

output:

yes

result:

ok single line: 'yes'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3692kb

input:

9 12
R...K.....KK
...KKK.T..KK
...K......KK
...K......KK
.....K....KK
..........KK
KK.......KKK
.KK...K..KKK
..K......KKK

output:

yes

result:

ok single line: 'yes'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

17 14
......KK......
......KK......
RKK...KK......
K.....KKKK...K
......KKKK..KK
......KKKK..KK
...KKKKK.....K
..K.KKKKK.....
............K.
............K.
....K.........
...........KK.
KKKKKKKKKK.KK.
KK..KKKKK.....
T.............
...K.......K..
.........KKKKK

output:

yes

result:

ok single line: 'yes'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

10 10
.K.K.K.K.T
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
R.K.K.K.K.

output:

no

result:

ok single line: 'no'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3792kb

input:

4 3
K.T
...
.K.
R..

output:

no

result:

ok single line: 'no'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

4 3
..T
...
.K.
R..

output:

yes

result:

ok single line: 'yes'

Test #17:

score: 0
Accepted
time: 47ms
memory: 6000kb

input:

500 500
R..KK..................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #18:

score: 0
Accepted
time: 53ms
memory: 5968kb

input:

500 500
R..KK..................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #19:

score: 0
Accepted
time: 11ms
memory: 8252kb

input:

742 741
KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...

output:

no

result:

ok single line: 'no'

Test #20:

score: 0
Accepted
time: 14ms
memory: 8184kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

no

result:

ok single line: 'no'

Test #21:

score: 0
Accepted
time: 9ms
memory: 8104kb

input:

742 741
KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...

output:

yes

result:

ok single line: 'yes'

Test #22:

score: 0
Accepted
time: 23ms
memory: 8248kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #23:

score: 0
Accepted
time: 22ms
memory: 8872kb

input:

750 750
R.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.KKK.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K....

output:

yes

result:

ok single line: 'yes'

Test #24:

score: 0
Accepted
time: 25ms
memory: 8704kb

input:

750 750
R.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.KKK.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.KKK.K.KKK.K.K.K.K.K.KKK.K.K.K.K....

output:

yes

result:

ok single line: 'yes'

Test #25:

score: 0
Accepted
time: 88ms
memory: 9012kb

input:

750 750
R.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....

output:

no

result:

ok single line: 'no'

Test #26:

score: 0
Accepted
time: 58ms
memory: 8828kb

input:

750 750
R.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....

output:

no

result:

ok single line: 'no'

Test #27:

score: 0
Accepted
time: 6ms
memory: 8056kb

input:

744 750
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #28:

score: 0
Accepted
time: 29ms
memory: 8816kb

input:

747 747
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #29:

score: 0
Accepted
time: 39ms
memory: 8704kb

input:

748 748
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #30:

score: 0
Accepted
time: 326ms
memory: 11948kb

input:

750 750
.......................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #31:

score: 0
Accepted
time: 715ms
memory: 9224kb

input:

750 750
.....................K........................................................................................................K................................................................................................................................................K.......................

output:

yes

result:

ok single line: 'yes'

Test #32:

score: 0
Accepted
time: 444ms
memory: 8956kb

input:

750 750
.....................K................................................................................K.......................K.K..............................................................................................................................................K.......................

output:

yes

result:

ok single line: 'yes'

Test #33:

score: 0
Accepted
time: 165ms
memory: 8796kb

input:

750 750
..K........K..K......K.....................K.........................K.....................K..........K.......................K.K..............................................................................................................................................K.......................

output:

yes

result:

ok single line: 'yes'

Test #34:

score: 0
Accepted
time: 694ms
memory: 9292kb

input:

750 750
.....................K........................................................................................................K................................................................................................................................................K.......................

output:

no

result:

ok single line: 'no'

Test #35:

score: 0
Accepted
time: 389ms
memory: 8924kb

input:

750 750
.....................K................................................................................K.......................K.K..............................................................................................................................................K.......................

output:

no

result:

ok single line: 'no'

Test #36:

score: 0
Accepted
time: 153ms
memory: 8808kb

input:

750 750
..K........K..K......K.....................K.........................K.....................K..........K.......................K.K..............................................................................................................................................K.......................

output:

no

result:

ok single line: 'no'

Test #37:

score: 0
Accepted
time: 596ms
memory: 11772kb

input:

750 750
.......................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #38:

score: 0
Accepted
time: 64ms
memory: 8656kb

input:

750 750
K........K..................K.................................K...........KK..........................................K...........K.....K.......K.............................K.................................K.............................................K...............K........................

output:

yes

result:

ok single line: 'yes'

Test #39:

score: 0
Accepted
time: 202ms
memory: 8932kb

input:

750 750
....................................................................................................................................................................................................................................................................................K..................

output:

yes

result:

ok single line: 'yes'

Test #40:

score: 0
Accepted
time: 76ms
memory: 8752kb

input:

750 750
......K....K.................................K...........K.......K..............K.............................................K.................................................K...K.....................................KK............K....................................K...KK.K..................

output:

yes

result:

ok single line: 'yes'

Test #41:

score: 0
Accepted
time: 83ms
memory: 8768kb

input:

750 750
K........K..................K.................................K...........KK..........................................K...........K.....K.......K.............................K.................................K.............................................K...............K........................

output:

no

result:

ok single line: 'no'

Test #42:

score: 0
Accepted
time: 5ms
memory: 8048kb

input:

750 750
......K.K..................K......K...K...............K..K............K.........K...............................................................K.....K...............K..K..................................K..K...K..........K....................K.........KKK............................K.K..K.....

output:

no

result:

ok single line: 'no'

Test #43:

score: 0
Accepted
time: 82ms
memory: 8808kb

input:

750 750
......K....K.................................K...........K.......K..............K.............................................K.................................................K...K.....................................KK............K....................................K...KK.K..................

output:

no

result:

ok single line: 'no'

Test #44:

score: 0
Accepted
time: 2649ms
memory: 11224kb

input:

750 750
R..KK..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K.....

output:

yes

result:

ok single line: 'yes'

Test #45:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

6 6
.....T
..K.K.
K.K...
....K.
R..K..
....K.

output:

yes

result:

ok single line: 'yes'

Test #46:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

3 4
RK..
KK..
...T

output:

yes

result:

ok single line: 'yes'

Test #47:

score: 0
Accepted
time: 2ms
memory: 3796kb

input:

4 4
.K..
KR..
K...
.K.T

output:

no

result:

ok single line: 'no'