제출 #693697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
693697		Kongggwp	Mecho (IOI09_mecho)	C++14	84 / 100	268 ms	11220 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
int dx[] = {0,1,0,-1} , dy[] = {1,0,-1,0} ,x ,y , st ,N , si , sj , fi , fj;
const int n=801;
char s[n][n];
vector<vector<int>>timebee(n , vector<int>(n,INT_MAX));
vector<vector<int>>timebear(n , vector<int>(n,INT_MAX));
vector<vector<int>>visbee(n , vector<int>(n,0));
queue<pair<pair<int,int>,int>>qbear,qbee;

int check(int m)
{
    //cout << m << endl;
    if(m>timebee[fi][fj])return 0;
    while(!qbear.empty())qbear.pop();
    for(int i=0 ; i<N ; i++)for(int j=0 ; j<N ; j++)timebear[i][j]=INT_MAX;
    vector<vector<int>>visbear(N , vector<int>(N,0));
    qbear.push({{si,sj},0});
    timebear[si][sj] = m;
    visbear[si][sj] = 1;
    while(!qbear.empty())
    {
        int r = qbear.front().first.first , c = qbear.front().first.second , time = qbear.front().second;
        //cout << r << " " << c << " " << time << endl;
        qbear.pop();
        if(timebear[r][c]==INT_MAX)continue;
        for(int i=0 ; i<4 ; i++)
        {
            int nr = r+dx[i];
            int nc = c+dy[i];
            if(nr<0 or nr>=N or nc<0 or nc>=N or s[nr][nc]=='T' or s[nr][nc]=='H' or visbear[nr][nc]==1)continue;
            if((time+1)%st==0)timebear[nr][nc]=timebear[r][c]+1;
            else timebear[nr][nc]=timebear[r][c];
            if(timebee[nr][nc]<=timebear[nr][nc])continue;
            visbear[nr][nc]=1;
            qbear.push({{nr,nc},time+1});
        }
    }
    /*for(int i=0 ; i<N ; i++)
    {
        for(int j=0 ; j<N ; j++)
        {
            if(timebear[i][j]!=INT_MAX)cout << timebear[i][j];
            else cout << 0;
        }
        cout << endl;
    }
    cout << endl;
    for(int i=0 ; i<N ; i++)
    {
        for(int j=0 ; j<N ; j++)
        {
            if(timebee[i][j]!=INT_MAX)cout << timebee[i][j];
            else cout << 0;
        }
        cout << endl;
    }*/
    if(timebear[fi][fj]!=INT_MAX)return 1;
    else return 0;
}

int main()
{
    cin >> N >> st;
    for(int i=0 ; i<N ; i++)
    {
        for(int j=0 ; j<N ; j++)
        {
            cin >> s[i][j];
            if(s[i][j]=='M')
            {
                si=i;
                sj=j;
            }
            if(s[i][j]=='D')
            {
                fi=i;
                fj=j;
            }
            if(s[i][j]=='H')
            {
                qbee.push({{i,j},0});
                visbee[i][j] = 1;
                timebee[i][j]=0;
            }
        }
    }

    while(!qbee.empty())
    {
        int r = qbee.front().first.first , c = qbee.front().first.second , time = qbee.front().second;
        qbee.pop();
        for(int i=0 ; i<4 ; i++)
        {
            int nr = r+dx[i];
            int nc = c+dy[i];
            if(nr<0 or nr>=N or nc<0 or nc>=N or s[nr][nc]=='D' or s[nr][nc]=='T' or visbee[nr][nc])continue;
            visbee[nr][nc]=1;
            timebee[nr][nc] = time+1;
            qbee.push({{nr,nc},timebee[nr][nc]});
        }
    }
    int l=0 ,r=N*N , m ,ans=-1;
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(check(m))ans=m , l=m+1;
        else r=m-1;
    }
    //check(2);
    cout << ans ;
}

• Subtask 1: 84 / 100