Cod sursa(job #495617)

Utilizator attila3453Geiszt Attila attila3453 Data 26 octombrie 2010 09:17:05
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <limits.h>

using namespace std;

ifstream fi("rj.in");
ofstream fo("rj.out");

const int nmax = 101;
const int dir = 8;

int n, m, xr, yr, xj, yj;

int dy[dir]= {0, 1, 0, -1, -1, 1, -1, 1};
int dx[dir]= {1, 0, -1, 0, -1, 1,  1,-1};

int r[nmax][nmax];
int j[nmax][nmax];

char A[nmax][nmax];

struct Punct
{
    int x, y;
} C[nmax * nmax], p;

void citire ()
{
    int i, k;

    char c;

    fi >> n >> m;

    for (i = 0; i <= n+1; i++)
        A[i][0]=A[i][m+1]='X';

    for (i=0; i<=m+1; i++)
        A[0][i]=A[n+1][i]='X';

    fi.get(c);

    for (i=1; i<=n; i++)
    {
        for (k=1; k<=m; k++)
        {
            fi.get(c);

            switch(c)
            {
                case 'R':
                    xr=i;
                    yr=k;
                break;

                case 'J':
                    xj=i;
                    yj=k;
                break;

                default:
                    A[i][k]=c;
                break;
            }
        }

        fi.get(c);
    }

    fi.close();
}

void parcurge (int x0, int y0, int d[nmax][nmax])
{
    int inc=0, sf=0, i, k;

    for (i = 0; i <= n + 1; i++)
        for (k = 0; k <= m + 1; k++)
            d[i][k] = -1;

    C[0].y=x0;
    C[0].x=y0;

    d[x0][y0]=1;

    while (inc<=sf)
    {
        p=C[inc];

        inc++;

        for (i = 0; i < dir; i++)
        {
            int x, y;

            x = p.x+dx[i];
            y = p.y+dy[i];

            if (A[y][x]== ' ' &&
                d[y][x]== -1)
            {
                d[y][x]= 1 + d[p.y][p.x];

                sf++;

                C[sf].y = y;
                C[sf].x = x;
            }
        }
    }
}

void afisare(int j[nmax][nmax])
{
    int tmin= INT_MAX, xmin = -1, ymin = -1, i, k;

    for (i = 1; i <= n; i++)
        for (k = 1; k <= m; k++)
            if (r[i][k] == j[i][k])
                if (r[i][k] != -1 &&
                    r[i][k] < tmin)
                {
                    tmin=r[i][k];

                    xmin=i;
                    ymin=k;
                }

    fo << tmin << ' ' << xmin << ' '<< ymin << '\n';

    fo.close ();
}

int main()
{
    citire();
    parcurge(xr, yr, r);
    parcurge(xj, yj, j);
    afisare(j);
    return 0;
}