QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53278#2213. KnightSilent_AshWA 44ms22444kbC++2.1kb2022-10-04 21:13:592022-10-04 21:14:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-04 21:14:02]
  • 评测
  • 测评结果:WA
  • 用时:44ms
  • 内存:22444kb
  • [2022-10-04 21:13:59]
  • 提交

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 << 1] ;
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] ;
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[i] == '@') mp[i][j] = 0 ;
			else mp[i][j] = 1 ;
			if(mp[i][j] == 'A') A = (i - 1) * n + j ;
			else if(mp[i][j] == 'B') B = (i - 1) * n + j ;
		}
	}
	
	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) ;
		}
	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] ^ 1) != cl[B]) cout << "Alice\n" ;
	else cout << "Bob\n" ;
	return 0 ;
}


Details

Test #1:

score: 0
Wrong Answer
time: 44ms
memory: 22444kb