QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53308 | #2213. Knight | Silent_Ash | WA | 205ms | 70860kb | C++ | 2.4kb | 2022-10-04 21:38:12 | 2022-10-04 21:38:13 |
Judging History
answer
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 5 ;
const int M = 1e6 + 5 ;
int rd()
{
int res = 0 , f = 1 ;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1 ; ch = getchar() ;}
while(ch >= '0' && ch <= '9')res = (res << 1) + (res << 3) + (ch ^ 48) , ch = getchar() ;
return res * f ;
}
struct Edge
{
int from , to , w , next_ ;
Edge(){}
Edge(int a , int b , int c , int d):from(a),to(b),w(c),next_(d){} ;
} ;
Edge edge[M << 3] ;
int head[M << 1] , size_ ;
void add_(int from , int to , int w)
{
edge[++size_] = Edge(from , to , w , head[from]) ;
head[from] = size_ ;
}
void clear()
{
memset(head , 0 , sizeof head) ;
size_ = 0 ;
}
int mp[N][N] ;
int n , m , c , r ;
char s[N] ;
pair<int , int> A , B ;
int cl[M] , col = 2 ;
void dfs(int u , int col)
{
if(cl[u]) return ;
cl[u] = col ;
for(int i = head[u] ; i ; i = edge[i].next_)
{
int v = edge[i].to ;
dfs(v , col ^ 1) ;
}
}
int main()
{
n = rd() ; m = rd() ; c = rd() ; r = rd() ;
int dx[] = {c , -c , c , -c , r , -r , r , -r} ;
int dy[] = {r , -r , -r , r , c , -c , -c , c} ;
for(int i = 1 ; i <= n ; i++)
{
scanf("%s" , s + 1) ;
for(int j = 1 ; j <= m ; j++)
{
if(s[j] == '@') mp[i][j] = 0 ;
else mp[i][j] = 1 ;
if(s[j] == 'A') A = {i , j} ;
else if(s[j] == 'B') B = {i , j} ;
}
}
int f = 1 ;
for(int t = 0 ; t < 8 ; t++)
{
int tx = dx[t] + A.first , ty = dy[t] + A.second ;
if(tx < 0 || ty < 0 || tx > n || ty > m || !mp[tx][ty]) continue ;
f = 0 ; break ;
}
if(f){cout << "Bob\n" ; return 0 ;}
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
if(mp[i][j]) for(int id = (i - 1) * n + j , t = 0 ; t < 8 ; t++)
{
int tx = dx[t] + i , ty = dy[t] + j ;
if(tx < 0 || ty < 0 || tx > n || ty > m || !mp[tx][ty]) continue ;
int to = (tx - 1) * n + ty ;
add_(id , to , 0) ; add_(to , id , 0) ;
}
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
{
int id = (i - 1) * n + j ;
if(!cl[id]) dfs(id , col) , col += 2 ;
}
if((cl[(A.first - 1) * n + A.second] ^ 1) != (cl[(B.first - 1) * n + B.second] ^ 1)) cout << "Alice\n" ;
else cout << "Bob\n" ;
return 0 ;
}
詳細信息
Test #1:
score: 100
Accepted
time: 5ms
memory: 6268kb
Test #2:
score: 0
Accepted
time: 3ms
memory: 4548kb
Test #3:
score: 0
Accepted
time: 205ms
memory: 70860kb
Test #4:
score: -100
Wrong Answer
time: 77ms
memory: 34832kb