Cod sursa(job #3153900)

Utilizator vlad_dimuVlad Dimulescu vlad_dimu Data 1 octombrie 2023 21:44:46
Problema Barbar Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <bits/stdc++.h>
#define MAXN 1000
using namespace std;

ifstream fin( "barbar.in" );
ofstream fout( "barbar.out" );

struct poz{
  int l, c;
};

int dl[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

int M, N;
int Drag[MAXN + 2][MAXN + 2]; //distanta minima pana la un dragon din poz (i, j)
int mat[MAXN + 2][MAXN + 2];
int flag;

poz in, out;

queue <poz> q;

void dfs( poz pos, int val ){
  mat[pos.l][pos.c] = 1;
  for( int i = 0; i < 4; i++ )
    if( mat[pos.l + dl[i]][pos.c + dc[i]] == 0 && Drag[pos.l + dl[i]][pos.c + dc[i]] >= val )
      dfs( {pos.l + dl[i], pos.c + dc[i]}, val );
}

int check( int val ){
  int i, j;
  for( i = 1; i <= M; i++ )
    for( j = 1; j <= N; j++ )
      if( mat[i][j] > 0 )
        mat[i][j] = 0;

  dfs( in, val );
  if( mat[out.l][out.c] == 1 )
    flag = 1;
  return mat[out.l][out.c];
}

int main(){
    int i, j, st, dr, mij;
    char ch;
    fin >> M >> N;
    for( i = 1; i <= M; i++ ){
      for( j = 1; j <= N; j++ ){
        fin >> ch;
        if( ch == '*' )
          Drag[i][j] = mat[i][j] = -1;
        else if( ch == 'I' )
          in = { i, j };
        else if( ch == 'O' )
          out = { i, j };
        else if( ch == 'D' )
          Drag[i][j] = 1, q.push( { i, j } );
      }
    }

    for( i = 0; i <= M + 1; i++ )
      Drag[i][0] = Drag[i][N + 1] = mat[i][0] = mat[i][N + 1] = -1;
    for( i  = 0; i <= N + 1; i++ )
      Drag[0][i] = Drag[M + 1][i] = mat[0][i] = mat[M + 1][i] = -1;

    do{
      poz top = q.front();
      q.pop();
      for( i = 0; i < 4; i++ ){
        if( Drag[top.l + dl[i]][top.c + dc[i]] == 0 )
          Drag[top.l + dl[i]][top.c + dc[i]] = Drag[top.l][top.c] + 1, q.push( { top.l + dl[i], top.c + dc[i] } );
      }
    }while( !q.empty() );

    st = 1; dr =  M + N + 1;
    while( dr - st > 1 ){
      mij = (st + dr) / 2;
      if( check( mij ) == 0 )
        dr = mij;
      else
        st = mij;
    }
    if( flag == 0 )
      fout << -1;
    else
      fout << st - 1;
}