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

luogu_hsy · 2025-10-30 20:51:29 · 题解

本人第一篇题解

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

大概整理一下

判定为不能落脚的格子，同样性质的还有边界外的格子。 至于障碍格,聪明的你一定发现了,障碍格对我们的做法几乎没有影响

而且,重点格与红色格子的性质相同!也就是说可以一步到达该格的起始格子非常肯定是绿色的格子了

首先,处理好每个红色格子，把满足条件的格子涂成绿色。

然后,寻找那些没有被涂色的格子，这些格子无论怎么走下一步都会走到绿色的格子，我们把这些格子涂成红色。

最后,返回第一步，处理还没处理过的红格。同时我们记录涂色格子的数量，当所有格子都被上色后，结束涂色操作

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

#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;
}

希望你们可以认可我的极品代码 求过