제출 #789051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789051		orcslop	Mecho (IOI09_mecho)	C++17	49 / 100	175 ms	6920 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 805; 
const int dx[4] = {-1, 1, 0, 0}; 
const int dy[4] = {0, 0, -1, 1}; 

int n, s; 
pair<int, int> mecho, home; 
queue<pair<int, int>> q; 
char grid[MAXN][MAXN]; 
int depth[2][MAXN][MAXN]; 

bool bbound(int x, int y){
    return (x >= 0 && y >= 0 && x < n && y < n && (grid[x][y] == 'G' || grid[x][y] == 'H' || grid[x][y] == 'M' || grid[x][y] == 'D')); 
}

bool mbound(int x, int y){
    return (x >= 0 && y >= 0 && x < n && y < n && (grid[x][y] == 'G' || grid[x][y] == 'M' || grid[x][y] == 'D')); 
}

bool check(int lim){
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) depth[1][i][j] = 0; 
    depth[1][mecho.first][mecho.second] = 1; 
    while(!q.empty()) q.pop(); 
    q.push(mecho); 

    while(!q.empty()){
        pair<int, int> curr = q.front(); 
        q.pop(); 
        for(int i = 0; i < 4; i++){
            int x = curr.first + dx[i]; 
            int y = curr.second + dy[i]; 
            int d = depth[1][curr.first][curr.second] + 1; 
            // cout << d << '\n'; 
            if(mbound(x, y) && !depth[1][x][y]){
                // cout << d << '\n'; 
                if((d - 1) / s + 1 + lim <= depth[0][x][y]){
                    depth[1][x][y] = d; 
                    q.push(make_pair(x, y)); 
                }
                if(x == home.first && y == home.second && (d - 1) / s + 1 + lim - ((d-1) % s == 0) <= depth[0][x][y]) return true; 

            }
        }
    }
    return depth[1][home.first][home.second]; 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> s; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> grid[i][j]; 
            if(grid[i][j] == 'H') {
                q.push(make_pair(i, j)); 
                depth[0][i][j] = 1; 
            }
            else if(grid[i][j] == 'M') mecho = make_pair(i, j); 
            else if(grid[i][j] == 'D') home = make_pair(i, j); 
        }
    }
    while(!q.empty()){
        pair<int, int> curr = q.front(); 
        q.pop(); 
        for(int i = 0; i < 4; i++){
            int x = curr.first + dx[i]; 
            int y = curr.second + dy[i]; 
            if(bbound(x, y) && !depth[0][x][y]){
                depth[0][x][y] = depth[0][curr.first][curr.second] + 1; 
                q.push(make_pair(x, y)); 
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) {
            // depth[1][i][j] = (depth[1][i][j] + s - 1) / s; 
            depth[0][i][j] -= (depth[0][i][j] > 0); 
        }
    }
    int low = -1, high = 5000; 
    while (low < high) {
        int mid = low + (high - low + 1) / 2;
        if (check(mid)) low = mid; 
        else high = mid - 1;
    }
    cout << (low) << '\n'; 
    // cout << check(3) << '\n'; 
    // for(int i = 0; i < n; i++){
    //     for(int j = 0; j < n; j++){
    //         cout << depth[0][i][j] << ' '; 
    //     }
    //     cout << "     "; 
    //     for(int j = 0; j < n; j++){
    //         cout << depth[1][i][j] << ' '; 
    //     }
    //     cout << '\n'; 

    // }
    return 0; 
}

• Subtask 1: 49 / 100