Submission #971388

#	Time	Username	Problem	Language	Result	Execution time	Memory
971388		meatball	Mecho (IOI09_mecho)	C++14	4 / 100	145 ms	6836 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first 
#define s second 
// https://oj.uz/problem/view/IOI09_mecho
const int MAX = 800;
char grid[MAX][MAX];
int n, s, dist[MAX][MAX],
    dr[4] = {1, -1, 0, 0},
    dc[4] = {0, 0, 1, -1};
pair<int, int> st, ed;

bool check(int mid) {
    int trav[n][n];
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            trav[i][j]=INT_MAX;
        }
    }
    queue<pair<int, int>> q;
    q.push(st);
    
    //trav: 剩餘時間
    trav[st.f][st.s]=mid*s; 
    while (!q.empty()) {
        pair<int, int> p=q.front(); q.pop();
        int r=p.f, c=p.s;
        if (grid[r][c]=='D') {  
            return true;
        }
        for (int i=0; i<4; i++) {
            int nr=r+dr[i], nc=c+dc[i];
            if (nr>=0 && nr<n && nc>=0 && nc<n && grid[nr][nc]!='T' && trav[nr][nc]==INT_MAX){
                trav[nr][nc]=trav[r][c]-1;
                if (trav[nr][nc]>dist[nr][nc]) {
                    q.push({nr, nc});
                }
            }
        }
    }
    return false; 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> s;
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            dist[i][j] = 2e9;
            if (grid[i][j] == 'H') {
                q.push({i, j});
                dist[i][j] = 0;
            } else if (grid[i][j] == 'M') {
                st = {i, j};
            } else if (grid[i][j] == 'D') {
                ed = {i, j};
            } 
        }
    }
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int r = p.f, c = p.s;
        for (int i = 0; i < 4; i++) {
            int r1 = r + dr[i], c1 = c + dc[i];
            if (r1 >= 0 && r1 < n && c1 >= 0 && c1 < n 
                && dist[r][c] + 1 < dist[r1][c1] &&
                grid[r1][c1] != 'T' && grid[r1][c1] != 'D') {
                dist[r1][c1] = dist[r][c] + 1;
                q.push({r1, c1});
            }
        }
    }
    int low = 0, high = dist[st.f][st.s] - 1;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (check(mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (check(low)) cout << low << '\n';
    else cout << -1 << '\n';
}

• Subtask 1: 4 / 100