Cod sursa(job #3154911)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 6 octombrie 2023 19:59:45
Problema Barbar Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>

using namespace std;

const int NMAX = 1005;
int n, m, startx, starty, endx, endy, pasi[NMAX][NMAX], dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};
bool v[NMAX][NMAX], viz[NMAX][NMAX];
vector<pair<int, int>> dragons;

bool ok(int i, int j)
{
    if(i > 0 && i <= n && j > 0 && j <= m)
        return true;
    return false;
}

void bfs_dragons(int dragonx, int dragony)
{
    queue<pair<int, int>> q;
    q.push({dragonx, dragony});

    pasi[dragonx][dragony] = 0;

    while(!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();

        for(int i = 0; i <= 3; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];

            if(pasi[xx][yy] > pasi[x][y] + 1 && ok(xx, yy) && !v[xx][yy])
            {
                q.push({xx, yy});
                pasi[xx][yy] = pasi[x][y] + 1;
            }
        }
    }
}

bool bfs_ans(int target)
{
    queue<pair<int, int>> q;

    q.push({startx, starty});
    if(pasi[startx][starty] < target)
        return false;
    viz[startx][starty] = true;

    while(!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();
        
        if(x == endx && y == endy)
            return true;
        for(int i = 0; i <= 3; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];

            if(pasi[xx][yy] >= target && ok(xx, yy) && !v[xx][yy] && !viz[xx][yy])
            {
                viz[xx][yy] = true;
                q.push({xx, yy});
            }
        }
    }

    return false;
}

int main()
{
    freopen("barbar.in", "r", stdin);
    freopen("barbar.out", "w", stdout);

    cin >> n >> m;
    char c;
    for(int i = 1; i <= n; i++)
    {
        memset(pasi[i], 1e6 + 5, sizeof(pasi[i]));
        for(int j = 1; j <= m; j++)
        {
            cin >> c;
            if(c == '*')
                v[i][j] = 1;

            if(c == 'I')
            {
                startx = i;
                starty = j;
            }
            
            if(c == 'O')
            {
                endx = i;
                endy = j;
            }

            if(c == 'D')
                dragons.push_back({i, j});
        }
    }

    for(int i = 0; i < dragons.size(); i++)
        bfs_dragons(dragons[i].first, dragons[i].second);

    int st = 1, dr = n * m, ans = 0;
    pasi[startx][starty] = 1e6 + 5;

    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(bfs_ans(mij))
        {
            ans = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
        for(int i = 1; i <= n; i++)
            memset(viz[i], false, sizeof(viz[i]));
    }
    cout << ans;
}