제출 #1038566

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

mecho

#include <bits/stdc++.h>

using namespace std;

struct Cell
{

int x, y, p;

};

int n;
int s;
char ma[801][801];
int enj[801][801];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool isvalid(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= n; 
}

bool monotone(int m)
{

queue<Cell> q;

for(int i = 1; i <= n; ++i)
{
    for(int j = 1; j <= n; ++j)
    {
        if(ma[i][j] == 'M')
        {
            Cell nodo;
            nodo.x = i;
            nodo.y = j;
            nodo.p = 0;
            q.push(nodo);
        }
    }
}

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

    for(int i = 0; i < 4; ++i)
    {
     
    for(int j = 1; j <= s; ++j)
    {
        int nx = Nodo.x + j * dx[i];
        int ny = Nodo.y + j * dy[i];

        if(!isvalid(nx, ny) && ma[nx][ny] == 'H' && ma[nx][ny] == 'T') break;

        if(m <= enj[nx][ny] && ma[nx][ny] != 'M')
        {
        if(ma[nx][ny] == 'D')
        {
            return true;
        }

        ma[nx][ny] = 'M';
        q.push({nx, ny, Nodo.p + 1});

        }

    
    }

    }

}

return false;

}

int BSOTA(int a, int b)
{

while(a + 1 < b)
{
    int m = (a + b) / 2;
    if(monotone(m))
    {
        a = m;
    }
    else
    {
        b = m;
    }
}

return a;

}

int main()
{

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

cin >> n >> s;

pair<int, int> pos;

queue<pair<int, int> > q;

for(int i = 1; i <= n; ++i)
{
    for(int j = 1; j <= n; ++j)
    {
        cin >> ma[i][j];
        if(ma[i][j] == 'H')
        {
            q.push(make_pair(i, j));
            enj[i][j] = 0;
        }
        else
        {
            enj[i][j] = INT_MAX;
        }
        if(ma[i][j] == 'M')
        {
            pos.first = i;
            pos.second = j;
        }
    }
}

while(!q.empty())
{
    int i2 = q.front().first, j2 = q.front().second;
    q.pop();

    for(int i = 0; i < 4; ++i)
    {
        int nx = dx[i] + i2;
        int ny = dy[i] + j2;

        if(isvalid(nx, ny) && ma[nx][ny] != 'D' && ma[nx][ny] != 'T' && ma[nx][ny] != 'H' && enj[nx][ny] == INT_MAX)
        {
            q.push(make_pair(nx, ny));
            enj[nx][ny] = enj[i2][j2] + 1;
        }
    }
}

int maxx = enj[pos.first][pos.second];

cout << BSOTA(0, maxx - 2);





}

• Subtask 1: 15 / 100