题解 AT2375 【Closed Rooms】

勿忘安己 · 2019-03-06 10:47:35 · 题解

题目大意

一个网格图，从一个起点出发。有些格子上锁。每一轮你都可以不断往一个已解锁的四个方向的相邻格子走，最多走k次走完后你可以选择至多k个未解锁的格子，将它们解锁。求最少多少轮，你能走到一个边界格子。

思路

因为只有第一次的前k次是无法自己解锁格子的，但是之后我们完全可以通过解锁格子然后走到任何地方（走的次数和可以解锁的次数相等），因此bfs求出第一轮能走到的格子，然后计算到边界最小轮数。

#include<bits/stdc++.h>
const int maxn=8e2+10;
using namespace std;
char a[maxn][maxn];
int stmp[maxn][maxn];//代表这是bfs的第几步
int direction[4][2]={1,0,-1,0,0,1,0,-1};//四个方向
int n,m,k;
int ans=99999999;
bool check(int x,int y)//判断这个点是否可行
{
    if(x>=0&&x<n&&y>=0&&y<m&&stmp[x][y]==0&&a[x][y]=='.')
    {
       return 1;
    }
    return 0;
}
queue<pair<int,int> >po;
int main()
{
    cin>>n>>m>>k;
    int sx,sy;
    getchar();
    for(int i=0;i<n;i++)//输入顺便找到起点
    {
        for(int j=0;j<m;j++)
        {
            scanf("%c",&a[i][j]);
            if(a[i][j]=='S')
            {
                sx=i;
                sy=j;
            }
        }
        getchar();
    }
    stmp[sx][sy]=1;
    po.push(make_pair(sx,sy));
    while(!po.empty())
    {
        int x=po.front().first;
        int y=po.front().second;
        ans=min(ans,min(min(x,n-x-1),min(y,m-y-1)));
        po.pop();
        for(int i=0;i<4;i++)
        {
            int xx=x+direction[i][0];
            int yy=y+direction[i][1];
            if(check(xx,yy)&&stmp[x][y]<=k)
            {
               stmp[xx][yy]=stmp[x][y]+1;
               po.push(make_pair(xx,yy));
            }
        }
    }
    int anss;
    anss=1+(ans+k-1)/k;//向上取整
    cout<<anss<<endl;
    return 0;
}