QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#17983 | #2213. Knight | A_Pikachu# | WA | 58ms | 11964kb | C++14 | 1.2kb | 2022-01-15 15:58:04 | 2022-05-04 16:34:46 |
Judging History
answer
#include <cstdio>
#include <queue>
using namespace std;
const int N=1005;
int n,m,r,c,xa,ya,xb,yb,cnt,sz[N*N],col[N][N];
int dx[]={-1,-1,1,1,-1,-1,1,1};
int dy[]={-1,1,-1,1,-1,-1,1,1};
char mp[N][N];
int abs(int x){return x<0?-x:x;}
struct node{
int x,y,t;
};
queue<node> q;
void bfs(int sx,int sy){
q.push((node){sx,sy,1});
col[sx][sy]=++cnt;
sz[cnt]=1;
while(!q.empty()){
node tmp=q.front(); q.pop();
int x=tmp.x,y=tmp.y,t=tmp.t;
for(int i=0; i<8; i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='@'||col[xx][yy]) continue;
col[xx][yy]=-1*t*cnt;
q.push((node){xx,yy,-1*t});
++sz[cnt];
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=0; i<4; i++) dx[i]*=r,dy[i]*=c;
for(int i=4; i<8; i++) dx[i]*=c,dy[i]*=r;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
scanf(" %c",&mp[i][j]);
if(mp[i][j]=='A') xa=i,ya=j;
if(mp[i][j]=='B') xb=i,yb=j;
}
}
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(!col[i][j]&&mp[i][j]!='@') bfs(i,j);
if(abs(col[xa][ya])!=abs(col[xb][yb])){
if(sz[abs(col[xa][ya])]==1) printf("Bob\n");
else printf("Alice\n");
}else{
if(col[xa][ya]==col[xb][yb]) printf("Alice\n");
else printf("Bob\n");
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 37ms
memory: 9956kb
Test #2:
score: 0
Accepted
time: 5ms
memory: 7604kb
Test #3:
score: 0
Accepted
time: 37ms
memory: 8688kb
Test #4:
score: 0
Accepted
time: 39ms
memory: 10028kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 5248kb
Test #6:
score: 0
Accepted
time: 12ms
memory: 9804kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 5288kb
Test #8:
score: 0
Accepted
time: 11ms
memory: 7780kb
Test #9:
score: 0
Accepted
time: 58ms
memory: 11964kb
Test #10:
score: 0
Accepted
time: 27ms
memory: 8552kb
Test #11:
score: 0
Accepted
time: 11ms
memory: 9508kb
Test #12:
score: 0
Accepted
time: 49ms
memory: 9348kb
Test #13:
score: -100
Wrong Answer
time: 6ms
memory: 8412kb