Cod sursa(job #2592455)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 1 aprilie 2020 18:28:01
Problema Barbar Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int NMAX = 1000;
const int MMAX = 1000;
const int INF = 2.e9;
int di[]= {-1 , 0 , 1 , 0};
int dj[]= {0 , 1 , 0 , -1};
struct dragoni
{
    int x , y;
};
dragoni temp1 , temp2;
int drg[NMAX + 5][MMAX + 5] , d[NMAX + 5][MMAX + 5] , n , m;
bool a[NMAX + 5][MMAX + 5];
char s[MMAX + 5];
int valid(int x , int y)
{
    if(x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == 0)
        return 1;
    return 0;
}
int main()
{
    freopen("barbar.in" , "r" , stdin);
    freopen("barbar.out" , "w" , stdout);
    int i , j , xs , ys , xf , yf;
    scanf("%d%d\n" , &n , &m);
    queue <dragoni> q;
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%s\n" , s);
        for(j = 0 ; j < m ; j ++)
        {
            drg[i][j + 1] = INF;
            if(s[j] == '*')
                a[i][j + 1] = 1;
            else if(s[j] == 'I')
            {
                xs = i;
                ys = j + 1;
            }
            else if(s[j] == 'O')
            {
                xf = i;
                yf = j + 1;
            }
            else if(s[j] == 'D')
            {
                temp1.x = i;
                temp1.y = j + 1;
                q.push(temp1);
                drg[i][j + 1] = 0;
            }
        }
    }
    while(!q.empty())
    {
        temp1 = q.front();
        q.pop();
        for(i = 0 ; i < 4 ; i ++)
        {
            temp2.x = temp1.x + di[i];
            temp2.y = temp1.y + dj[i];
            if(valid(temp2.x , temp2.y) && drg[temp2.x][temp2.y] > drg[temp1.x][temp1.y] + 1)
            {
                drg[temp2.x][temp2.y] = drg[temp1.x][temp1.y] + 1;
                q.push(temp2);
            }
        }
    }
    d[xs][ys] = drg[xs][ys];
    temp1.x = xs;
    temp1.y = ys;
    q.push(temp1);
    while(!q.empty())
    {
        temp1 = q.front();
        q.pop();
        for(i = 0 ; i < 4 ; i ++)
        {
            temp2.x = temp1.x + di[i];
            temp2.y = temp1.y + dj[i];
            if(valid(temp2.x , temp2.y) && drg[temp2.x][temp2.y] != 0 && d[temp2.x][temp2.y] < d[temp1.x][temp1.y] && d[temp2.x][temp2.y] < drg[temp2.x][temp2.y])
            {
                d[temp2.x][temp2.y] = min(drg[temp2.x][temp2.y] , d[temp1.x][temp1.y]);
                q.push(temp2);
            }
        }
    }
    //if(d[xf][yf] == 0)
        d[xf][yf] = -1;
    printf("%d\n" , d[xf][yf]);
    return 0;
}