제출 #693239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
693239		Sunbae	Mecho (IOI09_mecho)	C++17	53 / 100	140 ms	6880 KiB

mecho

#include <bits/stdc++.h>
#define infi INT_MAX
using namespace std;
using pii = pair<int,int>;
const int N = 800;
vector<pii>path = {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}}; 
int n, s;
char grid[N][N];
int bees[N][N];
bool vis[N][N];
int dist[N][N];
int sr, sc;
int dr, dc;
 
queue<pii>Q;
queue<pair<int, pii>>q;
bool Valid(int i, int j){
    return (i>=0 && j>=0 && i<n && j<n); 
}
void initial(int type){
    if(type == 0){
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                bees[i][j] = infi;
            }
        }
    }else if(type == 1){
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                dist[i][j] = infi;
            }
        }
    }
}
bool check(int wait){
    if(wait >= bees[sr][sc]) return false;
    memset(vis, false, sizeof(vis));
    initial(1);
    q.push({sr, {sc, 0}}); dist[sr][sc] = wait;
    while(!q.empty()){
        int i = q.front().first;
        int j = q.front().second.first;
        int cnt = q.front().second.second;
        q.pop(); 
        if(dist[i][j] == infi) continue;
        for(pii it: path){
            int x = i + it.first; int y = j + it.second;
            int distXY = dist[i][j] + ((cnt+1)%s == 0); 
            if(Valid(x, y) && !vis[x][y] && grid[x][y] != 'T' && distXY < bees[x][y]){
                dist[x][y] = distXY;
                vis[x][y] = true;
                q.push({x, {y, cnt+1}});
            }
        }
    }
    if(dist[dr][dc] == infi) return false;
    else return true; 
}
int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>s;
    initial(0); memset(vis, false, sizeof(vis));
    for(int i = 0; i<n; i++){
        string s; cin>>s;
        for(int j = 0; j<n; j++){
            grid[i][j] = s[j];
            if(grid[i][j] == 'M'){
                sr = i; sc = j;
            }else if(grid[i][j] == 'D'){
                dr = i; dc= j;
            }else if(grid[i][j] == 'H'){
                Q.push({i, j}); bees[i][j] = 0; vis[i][j] = true; 
            }
        } 
    }
    while(!Q.empty()){
        int i = Q.front().first; 
        int j = Q.front().second;
        Q.pop();
        for(pii it: path){
            int x = i + it.first; int y = j + it.second;
            if(Valid(x, y) && !vis[x][y] && grid[x][y] != 'T' && grid[x][y] != 'D'){
                vis[x][y] = true;
                bees[x][y] = bees[i][j] + 1; 
                Q.push({x, y}); 
            }
        }
    }
    int l = 0, h = 2*n;
    int ans = -1;
    while(l<=h){
        int mid = l + (h-l)/2;
        if(check(mid)){
            l = mid+1;
            ans = mid;
        }else{
            h = mid-1;
        }
    }
    cout<<ans;
}

• Subtask 1: 53 / 100