QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749588#2924. Lone RookzeyuAC ✓1471ms12476kbC++234.1kb2024-11-15 05:29:432024-11-15 05:29:43

Judging History

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

  • [2024-11-15 05:29:43]
  • 评测
  • 测评结果:AC
  • 用时:1471ms
  • 内存:12476kb
  • [2024-11-15 05:29:43]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pl pair<ll, ll>
#define pi pair<int, int>
#define minpq priority_queue<ll, vector<ll>, greater<ll>>
using namespace std;

#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
#endif

const ll mod = 1e9 + 7;

template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll gcd(ll a, ll b) {if(b == 0){return a;} return gcd(b, a % b);}

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;

bool ingrid(int r, int c){
	return r >= 0 && r < n && c >= 0 && c < m;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	vector<string> a(n);
	for (int i = 0; i < n; i ++) cin >> a[i];
	int attack[n][m], vis[n][m];
	memset(attack, 0, sizeof(attack));
	memset(vis, 0, sizeof(vis));
	pi s, e;
	for (int i = 0; i < n; i ++){
		for (int j = 0; j < m; j ++){
			if (a[i][j] == 'K'){
				for (int k = 0; k < 8; k ++){
					int ni = i + dx[k];
					int nj = j + dy[k];
					if (ingrid(ni, nj)){
						attack[ni][nj] ++;
					}
				}
			}
			if (a[i][j] == 'R'){
				s = {i, j};
			}
			if (a[i][j] == 'T'){
				e = {i, j};
			}
		}
	}
	queue<pi> que;
	que.push(s);
	vis[s.fi][s.se] = 1;
	while(! que.empty()){
		pi cur = que.front(); que.pop();
		int r = cur.fi, c = cur.se;
		//cout << r << ' ' << c << '\n';
		for (int i = r - 1; i >= 0; i --){
			if (a[i][c] == 'K' && attack[i][c] != 0) break;
			if (! vis[i][c] && attack[i][c] == 0){
				vis[i][c] = 1;
				que.push({i, c});
			}
		}
		for (int i = r + 1; i < n; i ++){
			if (a[i][c] == 'K' && attack[i][c] != 0) break;
			if (! vis[i][c] && attack[i][c] == 0){
				vis[i][c] = 1;
				que.push({i, c});
			}
		}
		for (int j = c - 1; j >= 0; j --){
			if (a[r][j] == 'K' && attack[r][j] != 0) break;
			if (! vis[r][j] && attack[r][j] == 0){
				vis[r][j] = 1;
				que.push({r, j});
			}
		}
		for (int j = c + 1; j < m; j ++){
			if (a[r][j] == 'K' && attack[r][j] != 0) break;
			if (! vis[r][j] && attack[r][j] == 0){
				vis[r][j] = 1;
				que.push({r, j});
			}
		}
		if (a[r][c] == 'K'){
			a[r][c] = '.';
			for (int k = 0; k < 8; k ++){
				int nr = r + dx[k];
				int nc = c + dy[k];
				if (ingrid(nr, nc)){
					attack[nr][nc] --;
					if (attack[nr][nc] == 0){
						bool havevis = false;
						for (int i = nr - 1; i >= 0; i --){
							if (a[i][nc] == 'K') break;
							if (vis[i][nc]) havevis = true;
						}
						for (int i = nr + 1; i < n; i ++){
							if (a[i][nc] == 'K') break;
							if (vis[i][nc]) havevis = true;
						}
						for (int j = nc - 1; j >= 0; j --){
							if (a[nr][j] == 'K') break;
							if (vis[nr][j]) havevis = true;
						}
						for (int j = nc + 1; j < m; j ++){
							if (a[nr][j] == 'K') break;
							if (vis[nr][j]) havevis = true;
						}
						if (havevis){
							vis[nr][nc] = 1;
							que.push({nr, nc});
						}
					}
				}
			}
		}
	}
	cout << (vis[e.fi][e.se] ? "yes" : "no");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3492kb

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

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

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

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

input:

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

output:

yes

result:

ok single line: 'yes'

Test #4:

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

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

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

input:

2 5
RKKK.
...KT

output:

no

result:

ok single line: 'no'

Test #6:

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

input:

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

output:

no

result:

ok single line: 'no'

Test #7:

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

input:

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

output:

no

result:

ok single line: 'no'

Test #8:

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

input:

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

output:

yes

result:

ok single line: 'yes'

Test #9:

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

input:

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

output:

no

result:

ok single line: 'no'

Test #10:

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

input:

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

output:

yes

result:

ok single line: 'yes'

Test #11:

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

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: 0ms
memory: 3496kb

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: 0ms
memory: 3628kb

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: 3596kb

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: 0ms
memory: 3552kb

input:

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

output:

no

result:

ok single line: 'no'

Test #16:

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

input:

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

output:

yes

result:

ok single line: 'yes'

Test #17:

score: 0
Accepted
time: 18ms
memory: 6084kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #18:

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

input:

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

output:

yes

result:

ok single line: 'yes'

Test #19:

score: 0
Accepted
time: 4ms
memory: 8448kb

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: 4ms
memory: 8520kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

no

result:

ok single line: 'no'

Test #21:

score: 0
Accepted
time: 8ms
memory: 8516kb

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: 8ms
memory: 8492kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #23:

score: 0
Accepted
time: 10ms
memory: 8524kb

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: 12ms
memory: 8656kb

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: 37ms
memory: 8812kb

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: 27ms
memory: 8900kb

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: 7ms
memory: 8764kb

input:

744 750
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #28:

score: 0
Accepted
time: 12ms
memory: 8520kb

input:

747 747
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #29:

score: 0
Accepted
time: 19ms
memory: 8540kb

input:

748 748
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #30:

score: 0
Accepted
time: 1471ms
memory: 12476kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #31:

score: 0
Accepted
time: 392ms
memory: 9144kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #32:

score: 0
Accepted
time: 233ms
memory: 8696kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #33:

score: 0
Accepted
time: 100ms
memory: 8660kb

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: 394ms
memory: 9084kb

input:

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

output:

no

result:

ok single line: 'no'

Test #35:

score: 0
Accepted
time: 229ms
memory: 8832kb

input:

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

output:

no

result:

ok single line: 'no'

Test #36:

score: 0
Accepted
time: 95ms
memory: 8844kb

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: 1351ms
memory: 11804kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #38:

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

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: 262ms
memory: 9188kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #40:

score: 0
Accepted
time: 56ms
memory: 8592kb

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: 55ms
memory: 8592kb

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: 0ms
memory: 8552kb

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: 53ms
memory: 8656kb

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: 1386ms
memory: 11292kb

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: 0ms
memory: 3792kb

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: 0ms
memory: 3632kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #47:

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

input:

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

output:

no

result:

ok single line: 'no'