Cod sursa(job #1570166)

Utilizator Ruben2015Parvu Ruben Ruben2015 Data 16 ianuarie 2016 11:20:10
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <cstring>
#define INF 199999

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int n, m, i, j, l;
int ij, jj, ir, jr, imin, jmin, minim;
char s[101];
int drum[101][101], drum2[101][101];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

bool verif(int x, int y)
{
    return (x >= 0 && x < n && y >= 0 && y < m);
}

void lee1()
{
    int b[2][7000], st = 0, dr = 0;
    int xx, yy, i, x, y;
    b[0][dr] = ir, b[1][dr] = jr;

    while (st <= dr)
    {
        x = b[0][st], y = b[1][st];
        for (i = 0; i < 8; i++)
        {
            xx = x + dx[i], yy = y + dy[i];
            if (drum[xx][yy] == INF && verif(xx, yy))
            {
                dr++;
                b[0][dr] = xx, b[1][dr] = yy;
                drum[xx][yy] = drum[x][y]+1;
            }
        }
        st++;
    }
}

void lee2()
{
    int b[2][7000], st = 0, dr = 0;
    int xx, yy, i, x, y;
    b[0][dr] = ij, b[1][dr] = jj;

    while (st <= dr)
    {
        x = b[0][st], y = b[1][st];
        for (i = 0; i < 8; i++)
        {
            xx = x + dx[i], yy = y + dy[i];
            if (drum2[xx][yy] == INF && verif(xx, yy))
            {
                dr++;
                b[0][dr] = xx, b[1][dr] = yy;
                drum2[xx][yy] = drum2[x][y]+1;
            }
        }
        st++;
    }
}

int main()
{


    f >> n >> m; f.get();
    for (i = 0; i < n; i++)
    {
        f.getline(s, m+1);
        l = strlen(s);
        for (j = 0; j < l; j++)
        {
            if (s[j] == 'X')
                drum[i][j] = drum2[i][j] = -1;
            else if (s[j] == ' ')
                drum[i][j] = drum2[i][j] = INF;
            else if (s[j] == 'R')
                drum[i][j] = 1, drum2[i][j] = INF, ir = i, jr = j;
            else if (s[j] == 'J')
                drum[i][j] = INF, drum2[i][j] = 1, ij = i, jj = j;
        }
    }

    lee1();
    lee2();
    minim = INF;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
            if (drum[i][j] == drum2[i][j] &&
                drum[i][j] < minim &&
                drum[i][j] > 0 && drum[i][j] != INF)
            {
                minim = drum[i][j];
                imin = i, jmin = j;
            }
    }

    g << minim << " " << imin+1 << " " << jmin+1;
    return 0;
}