Cod sursa(job #1837260)

Utilizator calinfloreaCalin Florea calinflorea Data 29 decembrie 2016 13:31:44
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <bits/stdc++.h>
#define inf 1000005
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
char d[1000005];
int n, m, b[105][105], c[105][105], minim = inf, minimi, minimj, r, a[105][105], xr, yr, xj, yj;
queue <pair<int,int> >q;
queue <pair<int,int> >t;
void Citire()
{
    int i, x, ii, jj;
    fin >> n >> m;
    ii=jj=0;
    while(fin.getline(d,105))
    {
        x = strlen(d);
        for(i = 0; i < x; i++)
        {
            if(d[i] == 'X')
              a[ii][jj] = -1;
            else if(d[i]=='R')
            {
                xr = ii;
                yr = jj;
                a[ii][jj] = 1;
            }
            else if(d[i]==' ')
                a[ii][jj] = 1;
            else if(d[i]=='J')
            {
                xj = ii;
                yj = jj;
                a[ii][jj] = 1;
            }
            jj++;
        }
        ii++;
        jj = 1;
    }

}
void Initializare()
{
    int i, j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            b[i][j] = c[i][j] = inf;
}
void Bordare()
{
    int i;
    for(i = 0; i <= n + 1; i++)
        a[i][0] = a[i][m + 1] = -1;
    for(i = 0; i <= m + 1; i++)
        a[0][i] = a[n + 1][i] = -1;
}
void LeeRomeo()
{
    int i, j, x, y, k;
    int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
    int dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};
    b[xr][yr] = 1;
    q.push(make_pair(xr,yr));
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for(k = 0; k < 8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if(a[x][y] != -1 && b[x][y] > b[i][j] + 1)
            {
                b[x][y] = b[i][j] + 1;
                q.push(make_pair(x,y));
            }
        }
    }

}
void LeeJulieta()
{
    int i, j, x, y, k;
    int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
    int dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};
    c[xj][yj] = 1;
    t.push(make_pair(xj,yj));
    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[x][y] != -1 && c[x][y] > c[i][j] + 1)
            {
                c[x][y] = c[i][j] + 1;
                t.push(make_pair(x,y));
            }
        }
    }
}
void Rezolva()
{
    int i, j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            if(c[i][j] == b[i][j] && minim > c[i][j])
                {
                    minimi = i;
                    minimj = j;
                    minim = c[i][j];
                }
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
            cout << c[i][j];
        cout << "\n";
    }
    cout << "\n\n\n\n\n";
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
            cout << b[i][j];
        cout << "\n";
    }
    fout << minim << " " << minimi << " " << minimj << "\n";
}
int main()
{
    Citire();
    Bordare();
    Initializare();
    LeeJulieta();
    LeeRomeo();
    Rezolva();
    return 0;
}