Cod sursa(job #78495)

Utilizator dominoMircea Pasoi domino Data 18 august 2007 09:07:28
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 105
#define FIN "rj.in"
#define FOUT "rj.out"
#define INF 0x3f3f3f3f
#define mp make_pair
#define f first
#define s second

const int di[] = {-1,+1, 0, 0,-1,-1,+1,+1};
const int dj[] = { 0, 0,-1,+1,-1,+1,-1,+1};

int N, M, R[MAX_N][MAX_N], J[MAX_N][MAX_N];
char A[MAX_N][MAX_N];
pair<int, pair<int, int> > Res;

void solve(int x, int y, int D[MAX_N][MAX_N])
{
    int i, j, ii, jj, d, ok;

    memset(D, 0x3f, MAX_N*MAX_N);
    D[x][y] = 1;

    for (ok = 1; ok; )
    {
        ok = 0;
        for (i = 0; i < N; ++i)
            for (j = 0; j < M; ++j)
            {
                if (D[i][j] == INF) continue;
                for (d = 0; d < 8; ++d)
                {
                    ii = i+di[d], jj = j+dj[d];
                    if (ii < 0 || jj < 0 || ii >= N || jj >= M || A[ii][jj] == 'X' || D[ii][jj] <= D[i][j]+1) continue;
                    D[ii][jj] = D[i][j]+1;
                    ok = 1;
                }
            }
    }
}

int main(void)
{
    int i, j;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d\n", &N, &M);
    for (i = 0; i < N; ++i)
        fgets(A[i], sizeof(A[0]), stdin);

    for (i = 0; i < N; ++i)
        for (j = 0; j < M; ++j)
        {
            if (A[i][j] == 'R') solve(i, j, R);
            if (A[i][j] == 'J') solve(i, j, J);
        }

    Res = mp(INF, mp(-1, -1));
    for (i = 0; i < N; ++i)
        for (j = 0; j < M; ++j)
        {
            if (A[i][j] != ' ') continue;
            if (R[i][j] != J[i][j]) continue;
            Res = min(Res, mp(R[i][j], mp(i, j)));
        }
    printf("%d %d %d\n", Res.f, Res.s.f+1, Res.s.s+1);
    
    return 0;
}