QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726470#2924. Lone Rookzeyu#WA 3ms13148kbC++234.3kb2024-11-09 01:12:132024-11-09 01:12:13

Judging History

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

  • [2024-11-09 01:12:13]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13148kb
  • [2024-11-09 01:12:13]
  • 提交

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);}

const int maxn = 1000010;
int n, m;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
vector<int> graph[maxn];
vector<bool> vis(maxn);

int id(int r, int c){
	return r * m + c;
}

int p[maxn], sz[maxn];

int find(int x){
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y){
	int px = find(x);
	int py = find(y);
	p[px] = py;
	sz[py] += sz[px];
}

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);
	for (int i = 0; i < maxn; i ++){
		p[i] = i; sz[i] = 1;
	}
	cin >> n >> m;
	vector<string> a(n);
	for (int i = 0; i < n; i ++) cin >> a[i];
	set<int> kid;
	int sid, eid;
	for (int i = 0; i < n; i ++){
		for (int j = 0; j < m; j ++){
			if (a[i][j] == 'K') kid.insert(id(i, j));
			if (a[i][j] == 'R') sid = id(i, j);
			if (a[i][j] == 'T') eid = id(i, j);
		}
	}
	for (int z : kid){
		for (int j = 0; j < 8; j ++){
			int nr = z / m + dx[j];
			int nc = z % m + dy[j];
			if (ingrid(nr, nc) && kid.find(id(nr, nc)) != kid.end()){
				merge(z, id(nr, nc));
			}
		}
	}
	for (int z : kid){
		if (sz[find(z)] == 1){
			int r = z / m, c = z % m;
			a[r][c] = '.';
		}
	}
	// for (int i = 0; i < n; i ++){
	// 	for (int j = 0; j < m; j ++) cout << a[i][j];
	// 	cout << '\n';
	// }
	vector<string> na = a;
	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)){
						na[ni][nj] = 'K';
					}
				}
			}
		}
	}
	a = na;
	int er = eid / m, ec = eid % m;
	if (a[er][ec] == 'K'){
		cout << "no";
		return 0;
	}
	// for (int i = 0; i < n; i ++){
	// 	for (int j = 0; j < m; j ++) cout << a[i][j];
	// 	cout << '\n';
	// }
	for (int i = 0; i < n; i ++){
		int s = 0, e = 0;
		while(s < m && e < m){
			while(s < m && a[i][s] == 'K') s ++;
			e = s + 1;
			while(e < m && a[i][e] == 'K') e ++;
			if (s < m && e < m){
				graph[id(i, s)].push_back(id(i, e));
				graph[id(i, e)].push_back(id(i, s));
			}
			s = e;
		}
	}
	for (int j = 0; j < m; j ++){
		int s = 0, e = 0;
		while(s < n && e < n){
			while(s < n && a[s][j] == 'K') s ++;
			e = s + 1;
			while(e < n && a[e][j] == 'K') e ++;
			if (s < n && e < n){
				graph[id(s, j)].push_back(id(e, j));
				graph[id(e, j)].push_back(id(s, j));
			}
			s = e;
		}
	}
	queue<int> que;
	que.push(sid);
	vis[sid] = true;
	while(! que.empty()){
		int q = que.front(); que.pop();
		for (int to : graph[q]){
			if (! vis[to]){
				que.push(to);
				vis[to] = true;
			}
		}
	}
	cout << (vis[eid] ? "yes" : "no");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

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

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

score: 0
Accepted
time: 3ms
memory: 11896kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #4:

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

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

score: -100
Wrong Answer
time: 3ms
memory: 12432kb

input:

2 5
RKKK.
...KT

output:

yes

result:

wrong answer 1st lines differ - expected: 'no', found: 'yes'