제출 #1276146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276146		k12_khoi	Mecho (IOI09_mecho)	C++17	84 / 100	172 ms	8860 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=805;
const int oo=1e9+1;
const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};

int n,mx_steps,start_x,start_y,l,r,mid,res;
pii new_dist;
int d[N][N];
pii dTwo[N][N];
char s[N][N];
queue <pii> q;

void pre_bfs()
{
    while (!q.empty()) q.pop();

    int u,v,x,y;

    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    if (s[i][j]=='H')
    {
        d[i][j]=0;
        q.push(make_pair(i,j));
    }
    else d[i][j]=oo+1;


    while (!q.empty())
    {
        u=q.front().X;
        v=q.front().Y;
        q.pop();

        for (int i=0;i<4;i++)
        {
            x=u+dx[i];
            y=v+dy[i];
            if (x>0 and x<=n and y>0 and y<=n and (s[x][y]=='G' or s[x][y]=='M') and d[x][y]>d[u][v]+1)
            {
                d[x][y]=d[u][v]+1;
                q.push(make_pair(x,y));
            }
        }
    }
}

bool check(int u,int v,int mid)
{
    while (!q.empty()) q.pop();

    int x,y;

    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    dTwo[i][j]=make_pair(oo,oo);

    dTwo[u][v]=make_pair(mid,0);
    q.push(make_pair(u,v));

    while (!q.empty())
    {
        u=q.front().X;
        v=q.front().Y;
        q.pop();

        new_dist=make_pair(dTwo[u][v].X,dTwo[u][v].Y+1);
        if (new_dist.Y==mx_steps)
        {
            new_dist.X++;
            new_dist.Y=0;
        }

        for (int i=0;i<4;i++)
        {
            x=u+dx[i];
            y=v+dy[i];
            if (x>0 and x<=n and y>0 and y<=n and (s[x][y]!='T' and s[x][y]!='H') and d[x][y]>new_dist.X and dTwo[x][y]>new_dist)
            {
                if (s[x][y]=='D') return true;
                dTwo[x][y]=new_dist;
                q.push(make_pair(x,y));
            }
        }
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> mx_steps;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    {
        cin >> s[i][j];

        if (s[i][j]=='M')
        {
            start_x=i;
            start_y=j;
        }
    }

    pre_bfs();

    res=-1;
    l=0;
    r=oo;
    while (l<=r)
    {
        mid=(l+r)/2;

        if (check(start_x,start_y,mid))
        {
            res=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    if (res==oo) res=-1;

    cout << res;
}

• Subtask 1: 84 / 100