QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80008 | #2924. Lone Rook | perspective | AC ✓ | 2649ms | 11948kb | C++23 | 4.8kb | 2023-02-21 16:49:51 | 2023-02-21 16:50:00 |
Judging History
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'