제출 #1156868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156868		catsarecool5530	Mecho (IOI09_mecho)	C++20	100 / 100	166 ms	11592 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n";
#define all(x) x.begin(), x.end()
const ll MOD = 1e9+7;
#define int long long
 
int n, s; 
string grid[800];
int beeTime[800][800];
int bearTime[800][800];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}
int goalX, goalY;
int startX, startY;
bool works(int waitTime) {
    if (beeTime[startX][startY] <= waitTime) {
        return false;
    }
    queue<array<int, 2>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            bearTime[i][j] = 1e9;
            if (grid[i][j] == 'M') {
                bearTime[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (inside(nx, ny) && bearTime[nx][ny] == (int) 1e9 && grid[nx][ny] != 'T'
            && (beeTime[nx][ny] * s > bearTime[x][y] + 1 + waitTime * s)) {
                bearTime[nx][ny] = bearTime[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return bearTime[goalX][goalY] != 1'000'000'000;

}

void solve() {
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            beeTime[i][j] = 1e9;
            if (grid[i][j] == 'H') {
                q.push({i, j});
                beeTime[i][j] = 0;
                
            }
            if (grid[i][j] == 'D') {
                goalX = i;
                goalY = j;
            }
            if (grid[i][j] == 'M') {
                startX = i;
                startY = j;
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (inside(nx, ny) && beeTime[nx][ny] == (int) 1e9 && grid[nx][ny] != 'T' && grid[nx][ny] != 'D') {
                beeTime[nx][ny] = beeTime[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    int l = 0, r = 1e9;
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (works(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << (beeTime[i][j] == 1e9 ? -1 : beeTime[i][j]) << " ";
    //     }
    //     cout << endl;
    // }
}



 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	// freopen("example.in", "r", stdin);
	//freopen("atlarge.out", "w", stdout);
	int t = 1; // cin >> t;
	while (t--) {
		solve();
	}

}

• Subtask 1: 100 / 100