제출 #1175785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175785		posn07	Mecho (IOI09_mecho)	C++20	0 / 100	117 ms	6296 KiB

mecho

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

struct Position {
    int x, y, time;
};

int N, S;
vector<string> forest;
vector<vector<int>> bee_time, mecho_time;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool is_valid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N && forest[x][y] != 'T';
}

void bfs_bees() {
    queue<Position> q;
    bee_time.assign(N, vector<int>(N, INT_MAX));
    
    // Start BFS from all hives
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (forest[i][j] == 'H') {
                q.push({i, j, 0});
                bee_time[i][j] = 0;
            }
        }
    }
    
    while (!q.empty()) {
        Position current = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = current.x + directions[i][0], ny = current.y + directions[i][1];
            if (is_valid(nx, ny) && forest[nx][ny] == 'G' && bee_time[nx][ny] == INT_MAX) {
                bee_time[nx][ny] = current.time + 1;
                q.push({nx, ny, current.time + 1});
            }
        }
    }
}

void bfs_mecho(int start_x, int start_y) {
    queue<Position> q;
    mecho_time.assign(N, vector<int>(N, INT_MAX));
    q.push({start_x, start_y, 0});
    mecho_time[start_x][start_y] = 0;
    
    while (!q.empty()) {
        Position current = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = current.x + directions[i][0], ny = current.y + directions[i][1];
            if (is_valid(nx, ny) && forest[nx][ny] == 'G' && mecho_time[nx][ny] == INT_MAX) {
                mecho_time[nx][ny] = current.time + 1;
                q.push({nx, ny, current.time + 1});
            }
        }
    }
}

int main() {
    cin >> N >> S;
    
    forest.resize(N);
    Position mecho_start, mecho_home;
    
    for (int i = 0; i < N; i++) {
        cin >> forest[i];
        for (int j = 0; j < N; j++) {
            if (forest[i][j] == 'M') {
                mecho_start = {i, j, 0};
            }
            if (forest[i][j] == 'D') {
                mecho_home = {i, j, 0};
            }
        }
    }

    bfs_bees();
    bfs_mecho(mecho_start.x, mecho_start.y);
    
    int low = 0, high = INT_MAX;
    int best_time = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        bool can_reach_home = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (forest[i][j] == 'G' && mecho_time[i][j] <= mid && bee_time[i][j] > mid) {
                    can_reach_home = true;
                }
            }
        }
        
        if (can_reach_home) {
            best_time = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << best_time << endl;
    return 0;
}

• Subtask 1: 0 / 100