Cod sursa(job #2536099)

Utilizator vladm98Munteanu Vlad vladm98 Data 1 februarie 2020 15:04:14
Problema Barbar Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>
using namespace std;
char matrix[1001][1001];
int distances[1001][1001];
bool verified[1001][1001];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
queue <pair<int, int>> coada;
bool isIn(int x, int y, int n, int m){
    return 1 <= x and x <= n and 1 <= y and y <= m;
}
void reseter(int n, int c){
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= c; ++j){
            verified[i][j] = false;
        }
    }
}
void LEE(int n, int c){
    while(coada.size()){
        pair <int, int> element = coada.front();
        int x = element.first;
        int y = element.second;
        coada.pop();
        for(int i = 0; i < 4; ++i){
            int newx = x + dx[i];
            int newy = y + dy[i];
            if(!isIn(newx, newy, n, c)) continue;
            if(verified[newx][newy]) continue;
            if(matrix[newx][newy] == '*') continue;
            verified[newx][newy] = true;
            distances[newx][newy] = distances[x][y] + 1;
            coada.push({newx, newy});
        }
    }
}
bool ALG(int n, int c, int startx, int starty, int finishx, int finishy, int value){
    verified[startx][starty] = true;
    coada.push({startx, starty});
    while(coada.size()){
        pair <int , int> element = coada.front();
        int x = element.first;
        int y = element.second;
        coada.pop();
        for(int i = 0; i < 4; ++i){
            int newx = x + dx[i];
            int newy = y + dy[i];
            if(!isIn(newx, newy, n, c)) continue;
            if(verified[newx][newy]) continue;
            if(matrix[newx][newy] == '*') continue;
            if(distances[newx][newy] < value) continue;
            if(newx == finishx and newy == finishy) {
                reseter(n, c);
                return true;
            }
            coada.push({newx, newy});
            verified[newx][newy] = true;
        }
    }
    reseter(n, c);
    return false;
}
int binarySearch(int n, int c, int startx, int starty, int finishx, int finishy){
    int current = 0;
    for(int power = 20; power >= 0; --power){
        if(current + (1 << power) <= distances[startx][starty] and ALG(n, c, startx, starty, finishx, finishy, current + (1 << power)))
            current += (1 << power);
    }
    return current;
}
ifstream fin ("barbar.in");
ofstream fout("barbar.out");

int main(){
    int n, c, startx, starty, finishx, finishy, ans;
    fin >> n >> c;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= c; ++j){
            fin >> matrix[i][j];
            if(matrix[i][j] == 'I'){
                startx = i;
                starty = j;
            }
            else if(matrix[i][j] == 'D'){
                coada.push({i, j});
                distances[i][j] = 0;
                verified[i][j] = true;
            }
            else if(matrix[i][j] == 'O') {
                finishx = i;
                finishy = j;
            }
        }
    }
    LEE(n, c);
    reseter(n, c);
    ans = binarySearch(n, c, startx, starty, finishx, finishy) ;
    if(ans >= 1) fout << ans ;
    else fout << "-1";
    return 0;
}