제출 #1038772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038772		Tepeyac	Mecho (IOI09_mecho)	C++11	100 / 100	143 ms	6376 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

int n, s;
char ma[802][802];
int enj[802][802];
int pa[802][802];

int r, c;
int r2, c2;

int mov[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

bool isvalidBee(int x, int y)
{
    if(!x || !y || x > n || y > n) 
    return false;

    if(ma[x][y] == 'T' || ma[x][y] == 'D') 
    return false;

    if(enj[x][y] != -1) 
    return false;

    return true;
}

void BeeFS()
{

    queue<pair<int, int> > q;
    pair<int, int> act;
    
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(ma[i][j] == 'H')
            {
                q.push({i, j});
            }
            else
            enj[i][j] = -1;
        }
    }

    while(!q.empty())
    {
        act = q.front();
        q.pop();

        for(int i = 0; i < 4; ++i)
        {
            int nx = act.first + mov[i][0];
            int ny = act.second + mov[i][1];

            if(isvalidBee(nx, ny))
            {
                enj[nx][ny] = enj[act.first][act.second] + s;
                q.push({nx, ny});
            }

        }

    }

}

bool isvalidMecho(int x, int y, int time)
{
    if(!x || !y || x > n || y > n) 
    return false;

    if(ma[x][y] == 'T')
    return false;

    if(ma[x][y] == 'D')
    return true;

    if(pa[x][y] != -1)
    return false;

    if(time >= enj[x][y])
    return false;

    return true;

}

bool monotone(int m)
{

    queue<pair<int, int> > q;
    pair<int, int> act;

    for( int i = 1; i <= n; i++ )
		for( int j = 1; j <= n; j++ )
			pa[i][j] = -1;

    q.push({r, c});
    pa[r][c] = m * s;

    if(enj[r][c] <= pa[r][c]) return false;

    while(!q.empty())
    {
        act = q.front();
        q.pop();

        int time = pa[act.first][act.second] + 1;

        for(int i = 0; i < 4; ++i)
        {
            int nx = act.first + mov[i][0];
            int ny = act.second + mov[i][1];

            if(isvalidMecho(nx, ny, time))
            {
                q.push({nx, ny});
                pa[nx][ny] = time;

            }
        }
    }

    return pa[r2][c2] != -1;

}

int Binary(int a, int b)
{
    while(a != b)
    {
        int m = (a + b) / 2 + 1;

        if(monotone(m))
        {
            a = m;
        }
        else
        b = m - 1;
    }
    return a;
}

int main()
{

cin.tie(0) -> sync_with_stdio(0);

cin >> n >> s;

for(int i = 1; i <= n; ++i)
{
    for(int j = 1; j <= n; ++j)
    {
        cin >> ma[i][j];
        if(ma[i][j] == 'M')
        {
            r = i, c = j;
        }
        if(ma[i][j] == 'D')
        {
            r2 = i, c2 = j;
        }
    }
}

BeeFS();

if(!monotone(0))
{
    cout << "-1\n"; return 0;
}


cout << Binary(0,  640000);

return 0;

}

• Subtask 1: 100 / 100