Cod sursa(job #1154724)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 26 martie 2014 12:46:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <cstdio>
#include <queue>
#include <utility>

using namespace std;

int n, m, lnR, colR, lnJ, colJ, rez = 0x3f3f3f3f, rezln, rezcol;
int H[110][110][2]; //0 - ROMEO, 1 - JULIETA
queue<pair<int, int> > Q;

//N NE E SE S SV V NV
const int dl[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    int i, j, ln, col;
    char c;

    scanf("%d %d\n", &n, &m);

    for (i = 1; i <= n; ++i, getchar())
        for (j = 1; j <= m; ++j)
        {
            c = getchar();
            if (c == 'X')
                H[i][j][0] = H[i][j][1] = -1;
            else if (c == 'R')
            {
                H[i][j][0] = 1;
                lnR = i, colR = j;
            }
            else if (c == 'J')
            {
                H[i][j][1] = 1;
                lnJ = i, colJ = j;
            }
        }

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

    Q.push(make_pair(lnR, colR));

    while(!Q.empty())
    {
        ln = Q.front().first, col = Q.front().second;
        for (i = 0; i < 8; ++i)
        {
            if (H[ln + dl[i]][col + dc[i]][0] == 0)
            {
                H[ln + dl[i]][col + dc[i]][0] = H[ln][col][0] + 1;
                Q.push(make_pair(ln + dl[i], col + dc[i]));
            }
        }
        Q.pop();
    }

    Q.push(make_pair(lnJ, colJ));

    while(!Q.empty())
    {
        ln = Q.front().first, col = Q.front().second;
        for (i = 0; i < 8; ++i)
        {
            if (H[ln + dl[i]][col + dc[i]][1] == 0)
            {
                H[ln + dl[i]][col + dc[i]][1] = H[ln][col][1] + 1;
                Q.push(make_pair(ln + dl[i], col + dc[i]));
            }
        }
        Q.pop();
    }

    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
        {
            if (H[i][j][0] != -1 && H[i][j][0] != 0 && H[i][j][0] == H[i][j][1] && rez > H[i][j][0])
            {
                rez = H[i][j][0];
                rezln = i, rezcol = j;
            }
        }

    printf("%d %d %d\n", rezln, rezcol, rez);
    fclose(stdout);
    return 0;
}