제출 #717752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717752		TheSahib	Mecho (IOI09_mecho)	C++17	100 / 100	168 ms	5068 KiB

mecho

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int oo = 1e9 + 9;
const int MAX = 801;


struct cord{
    int x = 0, y = 0;
    cord(int x1, int y1){
        x = x1;
        y = y1;
    }
};

pii dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int n, s;
cord start(0, 0), dest(0, 0);
char grid[MAX][MAX];

int beeTime[MAX][MAX];

bool inBounds(cord c){
    return c.x >= 0 && c.x < n && c.y >= 0 && c.y < n;
}

void bfs1(vector<cord>& source){
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
           beeTime[i][j] = oo;
        }
    }
    queue<cord> q;
    for(cord a:source){
        q.push(a);
        beeTime[a.x][a.y] = 0;
    }
    while(!q.empty()){
        cord c = q.front();
        q.pop();
        for(auto &d:dir){
            cord c1 = cord(c.x + d.first, c.y + d.second);
            if(!inBounds(c1) || grid[c1.x][c1.y] == 'T' || grid[c1.x][c1.y] == 'D') continue;

            if(beeTime[c1.x][c1.y] > beeTime[c.x][c.y] + 1){
                beeTime[c1.x][c1.y] = beeTime[c.x][c.y] + 1;
                q.push(c1);
            }
        }
    }
}


bool visited[MAX][MAX];
bool check(int startTime){
    memset(visited, 0, sizeof(visited));
    visited[start.x][start.y] = 1;

    queue<pair<cord, pii>> q;
    q.push({start, {startTime, s}});

    while(!q.empty()){
        cord c = q.front().first;
        pii t = q.front().second;
        q.pop();
        if(grid[c.x][c.y] == 'D') return true;
        if(beeTime[c.x][c.y] <= t.first) continue;

        for(auto d:dir){
            cord c1 = cord(c.x + d.first, c.y + d.second);
            if(!inBounds(c1) || grid[c1.x][c1.y] == 'T' || visited[c1.x][c1.y] == 1) continue;
            visited[c1.x][c1.y] = 1;
            if(t.second == 1){
                q.push({c1, {t.first + 1, s}});
            }
            else{
                q.push({c1, {t.first, t.second - 1}});
            }
        }
    }
    return false;
}


int main(){
    cin >> n >> s;
    vector<cord> bees;
    getchar();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            char c = getchar();
            grid[i][j] = c;
            if(c == 'H'){
                bees.push_back(cord(i, j));
            }
            else if(c == 'M'){
                start = cord(i, j);
            }
            else if(c == 'D'){
                dest = cord(i, j);
            }
        }
        getchar();
    }

    bfs1(bees);
    int l = 0, r = n * n;
    int ans = -1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    cout << ans << '\n';
}

• Subtask 1: 100 / 100