QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#17931#2213. Knightqingyu_orzTL 0ms0kbC++141.3kb2022-01-15 12:53:502022-05-04 16:26:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 16:26:54]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-01-15 12:53:50]
  • 提交

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(A==-1||B==-1)while(1);
	if(!g[A].size()||g[A][0]==B){
		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: 0
Time Limit Exceeded