QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726457 | #2924. Lone Rook | zeyu# | WA | 5ms | 13084kb | C++23 | 4.1kb | 2024-11-09 01:00:11 | 2024-11-09 01:00:11 |
Judging History
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;
// 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);
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: 5ms
memory: 12780kb
input:
2 2 KR TK
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 12424kb
input:
2 3 R.K KKT
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 4ms
memory: 11612kb
input:
5 3 KKT .K. K.. ... KKR
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 11644kb
input:
2 4 R.KK KK.T
output:
no
result:
ok single line: 'no'
Test #5:
score: -100
Wrong Answer
time: 5ms
memory: 13084kb
input:
2 5 RKKK. ...KT
output:
yes
result:
wrong answer 1st lines differ - expected: 'no', found: 'yes'