Cod sursa(job #1792433)

Utilizator vasi461Vasiliu Dragos vasi461 Data 30 octombrie 2016 14:15:03
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
using namespace std;

#define INF 10002
#define MAT 102

ifstream cin("rj.in");
ofstream cout("rj.out");

int n, m, d[MAT][MAT], e[MAT][MAT], x1, x2, y1, y2, b[MAT*MAT][2], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char s[MAT][MAT];

bool coord(int cx, int cy)
{
    return (cx > 0 and cx <= n and cy > 0 and cy <= m);
}

void dist(int x1, int y1, int d[MAT][MAT])
{
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(s[i][j] == ' ' or s[i][j] == 'R' or s[i][j] == 'J')
            {
                d[i][j] = INF;
            }
                else
                {
                    d[i][j] = 0;
                }
        }
    }
    int v = 0;
    int p = 1;
    v++;
    b[v][0] = x1;
    b[v][1] = y1;
    d[x1][y1] = 0;
    while(v >= p)
    {
        int x = b[p][0];
        int y = b[p][1];
        p++;
        for(int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(coord(nx, ny))
            {
                if(d[nx][ny] == INF)
                {
                    d[nx][ny] = d[x][y] + 1;
                    v++;
                    b[v][0] = nx;
                    b[v][1] = ny;
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    cin.getline(s[0], 102);
    for(int i = 1; i <= n; ++i)
    {
        cin.getline(s[i] + 1, m + 2);
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(s[i][j] == 'R')
            {
                x1 = i;
                y1 = j;
            }
            if(s[i][j] == 'J')
            {
                x2 = i;
                y2 = j;
            }
        }
    }
    dist(x1, y1, d);
    dist(x2, y2, e);
    int minim = INF, imin, jmin;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(d[i][j] == e[i][j] and d[i][j])
            {
                if(d[i][j] < minim)
                {
                    minim = d[i][j];
                    imin = i;
                    jmin = j;
                }
            }
        }
    }
    cout << minim << ' ' << imin << ' ' << jmin << '\n';
    return 0;
}