QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#96412#2924. Lone Rookmariam#WA 2ms3480kbC++174.7kb2023-04-13 21:05:232023-04-13 21:06:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-13 21:06:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3480kb
  • [2023-04-13 21:05:23]
  • 提交

answer



//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
#include <unordered_set>
#include <queue>
#include <map>
#include <cmath>
#include <climits>
#include <iomanip>
#include <unordered_map>
#include <stdio.h>
#include <stack>
#include <list>
#include "complex"
#include <assert.h>

#define el '\n'
#define ll long long
#define ld long double
using namespace std;
//
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//
//using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N = 2e5 + 5, mod = 1e9 + 7, MAX = 1e9 + 1, M = 1e5;
long double PI = 3.14159265358979323846;;
#define point  complex<long double>
#define vec(a, b) b-a
#define dot(a, b) (long double)(conj(a)*b).real()
#define cross(a, b) (long double)(conj(a)*b).imag()
#define length(a) (hypot((a).imag(), (a).real()))
#define angle(a) atan2((a).imag(), (a).real())
int h, w;
//char a[201][201];
//int dx[] = {0, 0, -1, 1, 1, -1, -1, 1}, dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
//int dx[] = {-1, -1, 0, 0, 1, 1}, dy[] = {-1, 0, -1, 1, 0, 1};
//
//bool valid(int i, int j) {
//    return (i < h && i >= 0 && j < w && j >= 0);
//}
//
//bool vis[201][201];

ll mul(ll a, ll b) {
    return ((a % mod) * (b % mod)) % mod;
}

ll add(ll a, ll b) {
    return ((a % mod) + (b % mod)) % mod;
}

ll sub(ll a, ll b) {
    return ((((a + mod) % mod) - ((b + mod) % mod)) + mod) % mod;
}

ll fastpow(ll b, ll p) {
    if (p == 0)
        return 1;
    if (p == 1) {
        return b;
    }
    ll hp = fastpow(b, p / 2);
    ll ans = ((hp % mod) * (hp % mod)) % mod;

    if (p % 2) {
        ans = (ans * b) % mod;
    }

    return ans % mod;
}
//
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
//
bool valid(int x,int y,int n,int m){
    return (x>-1&&y>-1&&x<n&&y<m);
}
//
struct node{
    int x,y;
};
vector<pair<int,int>>night = {{-2,1},{-2,-1},{2,1},{2,-1},{-1,2},{1,2},{-1,-2},{1,-2},};
//
void clear(vector<vector<int>>&vis,int x,int y,int n,int m){
    for(auto&i:night){
        int nx=i.first+x;
        int ny=i.second+y;
        //
        if(valid(nx,ny,n,m)){
            vis[nx][ny]--;
        }
    }
}
//
bool bfs(vector<vector<char>>&v,int n,int m){
    vector<vector<int>>vis(n,vector<int>(m));
    //
    node start;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(v[i][j]=='R'){
               start={i,j};
            }else if(v[i][j]=='K') {
                for (auto &it: night) {
                    int x = i + it.first;
                    int y = j + it.second;
                    //
                    if (valid(x, y, n, m)) {
                        vis[x][y]++;
                    }
                }
            }
        }
    }
    //
    queue<node>q;
    q.push(start);
    //
    while(q.size()){
        auto tp = q.front();
        q.pop();
        //
        for(int i=0;i<4;i++){
            if(!dx[i]){
                for(int dst=1;dst<=m;dst++){
                    int x = dx[i]+tp.x;
                    int y=dy[i]*dst+tp.y;
                    //
                    if(!valid(x,y,n,m))break;
                    if(v[x][y]=='T')return 1;

                    //
                    if(vis[x][y]>0||v[x][y]=='R')continue;
                    q.push({x,y});
                    bool br=0;
                    if(v[x][y]=='K'){
                        clear(vis,x,y,n,m);br=1;
                    }
                    v[x][y]='R';
                    if(br)break;
                }
            }else{
                for(int dst=1;dst<=n;dst++){
                    int x = dx[i]*dst+tp.x;
                    int y=dy[i]+tp.y;
                    //
                    if(!valid(x,y,n,m))break;
                    if(v[x][y]=='T')return 1;

                    //
                    if(vis[x][y]>0||v[x][y]=='R')continue;
                    if(v[x][y]=='T')return 1;
                    q.push({x,y});
                    bool br=0;
                    if(v[x][y]=='K'){
                        clear(vis,x,y,n,m);br=1;
                    }
                    v[x][y]='R';
                    if(br)break;
                }
            }
        }
    }
    return 0;
}
//
void m() {
    int n,m;
    cin>>n>>m;
    vector<vector<char>>v(n,vector<char>(m));
    for(auto&i:v)for(auto&j:i)cin>>j;
    //
    bool is=bfs(v,n,m);
    if(is)cout<<"yes\n";
    else cout<<"no\n";

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //   cin>>t;
    while (t--) {
        m();
    }

}

詳細信息

Test #1:

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

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

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

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

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

input:

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

output:

yes

result:

ok single line: 'yes'

Test #4:

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

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 3472kb

input:

2 5
RKKK.
...KT

output:

yes

result:

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