Submission #391380

#	Time	Username	Problem	Language	Result	Execution time	Memory
391380		ml1234	Mecho (IOI09_mecho)	C++17	27 / 100	1094 ms	6764 KiB

mecho

#include <iostream>
#include <string>
#include <queue>
using namespace std;
void floodfillbees(int i, int j);
bool validmecho(int i, int j);

string grid[800];
int bees[800][800];
int dx[] = {0, -1, 1, 0}, dy[] = {-1, 0, 0, 1};
int n, s;
int main() 
{
    cin >> n >> s;
    pair<int, int> mecho = {0, 0};
    int mechodist[800][800];
    for (int i = 0; i < n; i++)
    {
        cin >> grid[i];
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 'M')
            {
                mecho = {i, j};
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            bees[i][j] = 1e9;
            mechodist[i][j] = -1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 'H')
            {
                floodfillbees(i, j);
            }
        }
    }
    queue<pair<pair<int, int>, int>> q; //((i, j, min time difference along path)
    q.push({mecho, bees[mecho.first][mecho.second]});
    mechodist[mecho.first][mecho.second] = 0;
    int ans = 0;
    while (!q.empty())
    {
        int curri = q.front().first.first, currj = q.front().first.second;
        int mindiff = q.front().second;
        q.pop();
        if (grid[curri][currj] == 'D')
        {
            if (mindiff > 0)
            {
                ans = max(ans, mindiff / s);
            }
            continue;
        }
        for (int d = 0; d < 4; d++)
        {
            int nexti = curri + dx[d], nextj = currj + dy[d];
            if (!validmecho(nexti, nextj))
            {
                continue;
            }
            if (mechodist[nexti][nextj] == -1)
            {
                mechodist[nexti][nextj] = mechodist[curri][currj] + 1;
                q.push({{nexti, nextj}, min(mindiff, bees[nexti][nextj] - mechodist[nexti][nextj])});
            }
        }
    }
    cout << ans << endl;
    return 0;
}

bool ongrid(int i, int j)
{
    return (i >= 0 && i < n && j >= 0 && j < n);
}
bool validbees(int i, int j)
{
    return (ongrid(i, j) && !(grid[i][j] == 'T') && !(grid[i][j] == 'D') && !(grid[i][j] == 'H'));
}
bool validmecho(int i, int j)
{
    return (ongrid(i, j) && !(grid[i][j] == 'T'));
}

void floodfillbees(int i, int j)
{
    queue<pair<int, int>> q;
    q.push({i, j});
    bees[i][j] = 0;
    while (!q.empty())
    {
        int curri = q.front().first, currj = q.front().second;
        q.pop();
        for (int d = 0; d < 4; d++)
        {
            int nexti = curri + dx[d], nextj = currj + dy[d];
            if (validbees(nexti, nextj) && bees[nexti][nextj] > bees[curri][currj] + s)
            {
                bees[nexti][nextj] = bees[curri][currj] + s;
                q.push({nexti, nextj});
            }
        }
    }
}

• Subtask 1: 27 / 100