alexandrabeldik
Beldica Alexandra
• alexandrabeldik
logout | contul meu
infoarena informatica de performanta
infoarena
blog
forum
calendar
profilul meu
mesaje
Home
Arhiva de probleme
Arhiva educatională
Arhiva monthly
Arhiva ACM
Concursuri
Concursuri virtuale
Clasament
Articole
Downloads
Links
Documentaţie
Despre infoarena
Monitorul de evaluare
Trimite soluţii
Contul meu
! Cautare
 
In curand...
167612 membri inregistrati

15:31:31
Fii un bun infoarenaut! Implică-te!

Pagini recente » Barbar | Monitorul de evaluare | Borderou de evaluare (job #3247840) | Borderou de evaluare (job #3247435) | Cod sursa (job #3247435)

Cod sursa(job #3247435)
Utilizator	DinaLucaDina Franco Luca Andrei DinaLuca	Data	7 octombrie 2024 19:02:26
Problema	Barbar	Scor	100
Compilator	cpp-64	Status	done
Runda	Arhiva de probleme	Marime	2.9 kb
Raporteaza aceasta sursa
#include <bits/stdc++.h>
using namespace std;

char a[1002][1002];
int dist[1002][1002];
int n, m, maxdist = 0, gasit = -1;
int xs, ys, xf, yf;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
ifstream fin ("barbar.in");
ofstream fout ("barbar.out");
void Read()
{
    fin >> n >> m;
    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=m; j++)
        {
            fin >> a[i][j];
            dist[i][j] = 2e9;
            if (a[i][j] == 'I')
            {
                xs = i; ys = j;
            }
            else if (a[i][j] == 'O')
            {
                xf = i; yf = j;
            }
        }


}



void Board()
{
    for (int i = 0; i<= n + 1; i++)
        a[i][0] = a[i][m+1] = '*';
    for (int j = 0; j<= m + 1; j++)
        a[0][j] = a[n + 1][j] = '*';
}

void Lee()
{
   queue<pair<int, int>> q;
   for (int i = 1; i<=n;i++)
        for (int j = 1; j<=m; j++)
            if (a[i][j] == 'D')
            {
                q.push({i,j});
                dist[i][j] = 0;
            }
    while (!q.empty())
    {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        for (int k = 0; k<4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(a[x][y] != '*' && dist[x][y] > dist[i][j] + 1)
            {
                dist[x][y] = dist[i][j] + 1;
                q.push({x,y});
            }
        }
    }
}

void Fill(int xs, int ys, int mij)
{
    if (dist[xs][ys] < mij) return;
    dist[xs][ys] = -1;
    stack<pair<int,int>> st;
    st.push({xs,ys});
    while(!st.empty())
    {
        int i = st.top().first;
        int j = st.top().second;
        st.pop();
        for (int k = 0; k<4;k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (a[x][y] != '*' && dist[x][y] >= mij)
            {
                dist[x][y] = -1;
                st.push({x,y});
            }
        }
    }
}

bool Check(int mij)
{
    Fill(xs, ys, mij);
    if (dist[xf][yf] == -1) return true;
    return false;
}

void caut()
{
    int st = 0, dr = maxdist;
    int distcopy[1002][1002];
    for (int i = 1; i<=n; i++)
        for (int j = 1; j <=m; j++)
            distcopy[i][j] = dist[i][j];
    while (st <= dr)
    {
        int mij = (st+dr)/2;
        if (Check(mij))
        {
            gasit = mij;
            st = mij + 1;
        }
        else dr = mij - 1;

        for (int i = 1; i<=n; i++)
            for (int j = 1; j <=m; j++)
                dist[i][j] = distcopy[i][j];
    }

}
void Solve()
{
    Lee();
    for (int i = 1; i<=n;i++)
    {
        for (int j = 1; j<=m; j++)
        {
        if (dist[i][j] != 2e9) maxdist = max(dist[i][j], maxdist);
        }
    }
    caut();
    fout << gasit;
}
int main()
{
    Read();
    Board();
    Solve();




}
© 2004-2024 Asociatia infoarenaPrima paginaDespre infoarenaTermeni si conditiiContactSari la inceputul paginii ↑
Creative Commons LicenseCu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena
este publicat sub licenta Creative Commons Attribution-NonCommercial 2.5.