Cod sursa(job #3166435)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 8 noiembrie 2023 19:08:24
Problema Barbar Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <queue>
#include <cstring>
#define INF (1 << 30)
std::ifstream fin("barbar.in");
std::ofstream fout("barbar.out");
int n, m, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1}, A[101][101], dist[101][101], mat[101][101];
int xst, yst, xfin, yfin;
std::queue<std::pair<int, std::pair<int, int>>> Q;
void BFS(){
    while(!Q.empty()){
        int c = Q.front().first, x = Q.front().second.first, y = Q.front().second.second;
        for(int d = 0; d < 4; d++){
            int xn = x + dx[d], yn = y + dy[d];
            if(xn > n || yn > m || xn < 1 || yn < 1)
                continue;
            if(A[xn][yn] != 1 && A[xn][yn] != 2 && dist[xn][yn] > dist[x][y] + 1 && dist[xn][yn] != -1){
                dist[xn][yn] = dist[x][y] + 1;
                Q.push({dist[xn][yn], {xn, yn}});
            }
        }
        Q.pop();
    }
}
int computeDist(int value){
    memset(mat, 0, sizeof(mat));
    std::queue<std::pair<int, int>> Q;
    Q.push({xst, yst});
    mat[xst][yst] = 1;
    while(!Q.empty()){
        int x = Q.front().first, y = Q.front().second;
        Q.pop();
        for(int d = 0; d < 4; d++){
            int xn = x + dx[d], yn = y + dy[d];
            if(xn > n || yn > m || xn < 1 || yn < 1)
                continue;
            if(A[xn][yn] != 1 && A[xn][yn] != 2 && mat[xn][yn] == 0 && dist[xn][yn] >= value){
                mat[xn][yn] = mat[x][y] + 1;
                Q.push({xn, yn});
            }
        }
    }
    
    return ((mat[xfin][yfin]) ? true : false);
}
int main(){
    fin >> n >> m;
    char c;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin >> c;
            dist[i][j] = INF;
            if(c == '.')
                A[i][j] = 0;
            else if(c == '*')
                A[i][j] = 1, dist[i][j] = -1;
            else if(c == 'D')
                A[i][j] = 2, Q.push({0, {i, j}}), dist[i][j] = 0;
            else if(c == 'I') xst = i, yst = j;
            else if(c == 'O') xfin = i, yfin = j;
        } 
    }
    BFS();
    int mx_val = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            mx_val = std::max(mx_val, dist[i][j]);
    }
    
    int left = 1, right = mx_val, mn_dist = mx_val;
    while(left < right){
        int mid = (left + right) / 2;
        if(computeDist(mid))
            mn_dist = std::min(mn_dist, mid);
        if(mn_dist == -1) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    fout << mn_dist;
}