제출 #446110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446110		JovanB	Mecho (IOI09_mecho)	C++17	100 / 100	225 ms	10604 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

int mat[1000][1000];
int tajm[1000][1000];
int dist[1000][1000];
int si, sj;
int n, s;
const int INF = 1000000007;

bool moze(int dis, int i, int j, int t){
    if(i < 1 || i > n || j < 1 || j > n) return 0;
    if(mat[i][j] == -1) return 0;
    dis++;
    if(dis/s+t >= tajm[i][j]) return 0;
    if(dis >= dist[i][j]) return 0;
    dist[i][j] = dis;
    return 1;
}

bool bfs(int t){
    queue <pair <int, int>> q;
    q.push({si, sj});
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            dist[i][j] = INF;
        }
    }
    dist[si][sj] = 0;
    while(!q.empty()){
        int i = q.front().first;
        int j = q.front().second;
        int dis = dist[i][j];
        q.pop();
        if(mat[i][j] == 2) return 1;
        if(moze(dis, i-1, j, t)) q.push({i-1, j});
        if(moze(dis, i+1, j, t)) q.push({i+1, j});
        if(moze(dis, i, j-1, t)) q.push({i, j-1});
        if(moze(dis, i, j+1, t)) q.push({i, j+1});
    }
    return 0;
}

int main(){

    cin >> n >> s;
    queue <pair <int, int>> q;
    for(int i=1; i<=n; i++){
        string str;
        cin >> str;
        for(int j=0; j<n; j++){
            tajm[i][j+1] = INF;
            if(str[j] == 'T') mat[i][j+1] = -1;
            if(str[j] == 'H'){mat[i][j+1] = -2; q.push({i, j+1}); tajm[i][j+1] = 0;}
            if(str[j] == 'M'){mat[i][j+1] = 1; si = i; sj = j+1;}
            if(str[j] == 'D') mat[i][j+1] = 2;
        }
    }
    while(!q.empty()){
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        int tren = tajm[i][j];
        if(mat[i-1][j] > -1 && mat[i-1][j] < 2 && tajm[i-1][j] > tren+1){tajm[i-1][j] = tren+1; q.push({i-1, j});}
        if(mat[i+1][j] > -1 && mat[i+1][j] < 2 && tajm[i+1][j] > tren+1){tajm[i+1][j] = tren+1; q.push({i+1, j});}
        if(mat[i][j-1] > -1 && mat[i][j-1] < 2 && tajm[i][j-1] > tren+1){tajm[i][j-1] = tren+1; q.push({i, j-1});}
        if(mat[i][j+1] > -1 && mat[i][j+1] < 2 && tajm[i][j+1] > tren+1){tajm[i][j+1] = tren+1; q.push({i, j+1});}
    }
    int maxres=-1;
    int l=0, r = tajm[si][sj]-1;
    while(l <= r){
        int mid = (l+r)/2;
        if(bfs(mid)){maxres = mid; l = mid+1;}
        else r = mid-1;
    }
    cout << maxres;
    return 0;
}

• Subtask 1: 100 / 100