Cod sursa(job #1768585)

Utilizator calinfloreaCalin Florea calinflorea Data 1 octombrie 2016 10:55:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
queue<pair<int,int> >q;
queue<pair<int,int> >t;
char a[105][105];
int n,m,b[105][105],c[105][105];
void Citire()
{
    int i;
    fin>>n>>m;
    fin.get();
    for(i = 1; i <= n; i++)
        fin.getline(a[i]+1,101);
}
void Bordare()
{
    int i;
    for(i=0;i<=m+1;i++)
        a[0][i]=a[n+1][i]='x';
    for(i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]='x';
}
void Initializare()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            b[i][j]=c[i][j]=10000000;
}
void LeeRomeo()
{
    int dx[]={-1,0,1,0,-1,-1,1,1};
    int dy[]={0,1,0,-1,1,-1,1,-1};
    int i,j,x,y,k;
    while(!t.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            x=dx[k]+i;
            y=dy[k]+j;
            if(a[i][j]==' ' && b[x][y]>b[i][j]+1)
                {b[x][y]=b[i][j]+1;
                q.push(make_pair(x,y));}

        }
    }
}
void LeeJulieta()
{
    int dx[]={-1,0,1,0,-1,-1,1,1};
    int dy[]={0,1,0,-1,1,-1,1,-1};
    int i,j,x,y,k;
    while(!t.empty())
    {
        i=t.front().first;
        j=t.front().second;
        t.pop();
        for(k=0;k<8;k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if(a[i][j]==' ' && c[i][j]>c[x][y]+1)
                {c[i][j]=c[x][y]+1;
                t.push(make_pair(x,y));}
        }
    }
}
void Rezolvare()
{
    int i,j,minim=1000000,pozitie1=0,pozitie2=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
    {
        if(b[i][j]==c[i][j] && b[i][j]<minim)
            {
                minim=b[i][j];
                pozitie1=i;
                pozitie2=j;

            }
    }
    fout<<pozitie1<<" "<<pozitie2<<" "<<minim<<"\n";
}
int main()
{
    Citire();
    Bordare();
    Initializare();
    LeeRomeo();
    LeeJulieta();
    Rezolvare();
    return 0;
}