QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#17920 | #2213. Knight | qingyu_orz | WA | 289ms | 61332kb | C++14 | 1.2kb | 2022-01-15 12:15:22 | 2022-05-04 16:20:33 |
Judging History
answer
#include<bits/stdc++.h>
#define mk(x,y) ((x-1)*m+y)
using namespace std;
char s[1005][1005];
vector<int>g[1000005];
int mb[8][2];
int col[1000005];
void dfs(int x){
for(auto cu:g[x]){
if(col[cu])continue;
col[cu]=-col[x];
dfs(cu);
}
}
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
mb[0][0]=x,mb[0][1]=y;
mb[1][0]=-x,mb[1][1]=y;
mb[2][0]=x,mb[2][1]=-y;
mb[3][0]=-x,mb[3][1]=-y;
mb[4][0]=y,mb[4][1]=x;
mb[5][0]=-y,mb[5][1]=x;
mb[6][0]=y,mb[6][1]=-x;
mb[7][0]=-y,mb[7][1]=-x;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
if(s[i][j]!='@'){
for(int k=0;k<8;++k){
int dx=i+mb[k][0],dy=j+mb[k][1];
if(dx<1||dy<1||dx>n||dy>m)continue;
if(s[dx][dy]=='@')continue;
int u=mk(i,j),v=mk(dx,dy);
g[u].emplace_back(v);
g[v].emplace_back(u);
}
}
int A=-1,B=-1;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
if(s[i][j]=='A')A=mk(i,j);
else if(s[i][j]=='B')B=mk(i,j);
}
if(!g[A].size()){
puts("Bob");
return 0;
}
int N=mk(n,m);
for(int i=1;i<=N;++i)if(!col[i]){
col[i]=i;
dfs(i);
}
if(abs(col[A])!=abs(col[B]))puts("Alice");
else if(col[A]!=col[B])puts("Alice");
else puts("Bob");
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 67ms
memory: 43100kb
Test #2:
score: 0
Accepted
time: 6ms
memory: 28356kb
Test #3:
score: 0
Accepted
time: 289ms
memory: 61332kb
Test #4:
score: -100
Wrong Answer
time: 124ms
memory: 44584kb