专栏文章

题解：P12658 [KOI 2023 Round 1] 格子游戏

lluogu_hsy
P12658题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@ming7nhr
此快照首次捕获于
2025/12/02 01:54
3 个月前
此快照最后确认于
2025/12/02 01:54
3 个月前
查看原文

本人第一篇题解

### 大概思路大家可以去看liuhc123的思路,毕竟我个人感觉他的思路特别清晰

大概整理一下

判定为不能落脚的格子，同样性质的还有边界外的格子。 至于障碍格,聪明的你一定发现了,障碍格对我们的做法几乎没有影响
而且,重点格与红色格子的性质相同!也就是说可以一步到达该格的起始格子非常肯定是绿色的格子了
首先,处理好每个红色格子，把满足条件的格子涂成绿色。
然后,寻找那些没有被涂色的格子，这些格子无论怎么走下一步都会走到绿色的格子，我们把这些格子涂成红色。
最后,返回第一步，处理还没处理过的红格。同时我们记录涂色格子的数量，当所有格子都被上色后，结束涂色操作

接下来,就是你们最喜欢的题解了

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[500][500],tnt=1,q;
bool mapa[500][500];
void chuli_red(int x,int y)
{
	if(!a[x-1][y]&&mapa[x-1][y]){
		a[x-1][y]=1,tnt++;
	}
	
	if(!a[x][y-1]&&mapa[x][y-1]){
		a[x][y-1]=1,tnt++;
	}
	for(int i=1;i<=k;i++){
		if(x-i==0||y-i==0){
			break;
		}
		if(!a[x-i][y-i]&&mapa[x-i][y-i]){
			a[x-i][y-i]=1,tnt++;
		} 
			
	}	
}
bool pd(int x,int y){
	if(a[x][y]){
		return false;
	}
	if(!mapa[x][y]){
		return false;
	}
	if(!a[x+1][y]&&mapa[x+1][y]){
		return false;
	}
	if(!a[x][y+1]&&mapa[x][y+1]){
		return false;
	}
	for(int i=1;i<=k;i++){
		if(x+i>n||y+i>m){
			break;
		}
		if(!a[i+x][y+i]&&mapa[x+i][y+i]){
			return false;
		} 
			
	}
	return true;
}
int main(){
	cin>>n>>m>>k;
	memset(mapa,false,sizeof(mapa));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			char x;
			cin>>x;
			if(x=='.'){
				mapa[i][j]=true;
			}
			else {
				mapa[i][j]=false,a[i][j]=-1,tnt++;
			}
		}
	a[n][m]=2;
	chuli_red(n,m);
	while(tnt<(n*m))
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(pd(i,j))
				{
					tnt++;
					a[i][j]=2;
					chuli_red(i,j);
				}
	}
	cin>>q;
	for(int i=1;i<=q;i++)	
	{
		int x,y;
		cin>>x>>y;
		if(a[x][y]==1){
			cout<<"First"<<endl;
		}
		if(a[x][y]==2){
			cout<<"Second"<<endl;
		}
	}
	return 0;
}
希望你们可以认可我的极品代码 求过

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...