Cod sursa(job #820977)

Utilizator icb_mnStf Cic icb_mn Data 21 noiembrie 2012 15:03:09
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include<fstream>
#include<queue>
#define NMAX 105
using namespace std;
ifstream f("rj.in"); ofstream g("rj.out");
int n, m, r[NMAX][NMAX], jl[NMAX][NMAX];
char c;
int dl[8] = {-1,-1,-1,0,0,1,1,1};
int dc[8] = {0,-1,1,-1,1,-1,0,1};
struct puncte
{
    int l;
    int c;
}a;
queue<puncte>q;
int main()
{
    f>>n>>m;
    f.get();
    int xl , xc;
    for(int i = 0; i <= n + 1; ++i) r[i][0] = r[i][m + 1] = jl[i][0] = jl[i][m + 1] = -1;
    for(int j = 0; j <= m + 1; ++j) r[0][j] = r[n + 1][j] = jl[0][j] = jl[n + 1][j] = -1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            f.get(c);
            switch(c)
            {
                case 'R' : r[i][j] = 1, a.l = i, a.c = j, q.push(a);break;
                case 'J' : jl[i][j] = 1, xl = i, xc = j;break;
                case 'X' : jl[i][j] = r[i][j] = -1;break;
            }
        }
        if(c != '\n')f.get();
    }

    while(!q.empty())
    {
        a = q.front(); q.pop();
        int l = a.l;
        int c = a.c;
        for(int k = 0; k < 8; ++k)
        {
            int ll = l + dl[k];
            int cc = c + dc[k];
            if(!r[ll][cc])
            {
                a.l = ll;
                a.c = cc;
                q.push(a);
                r[ll][cc] = r[l][c] + 1;
            }
        }
    }
    a.l = xl; a.c = xc; q.push(a);
    while(!q.empty())
    {
        a = q.front(); q.pop();
        int l = a.l;
        int c = a.c;
        for(int k = 0; k < 8; ++k)
        {
            int ll = l + dl[k];
            int cc = c + dc[k];
            if(!jl[ll][cc])
            {
                a.l = ll;
                a.c = cc;
                q.push(a);
                jl[ll][cc] = jl[l][c] + 1;
            }
        }
    }
    int tmin = NMAX * NMAX, xmin = 0, ymin = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(r[i][j] == jl[i][j] && r[i][j] != -1 && r[i][j] != 0)
            {
                if(tmin > r[i][j])
                {
                    tmin = r[i][j];
                    xmin = i;
                    ymin = j;
                }
            }
    g<<tmin<<' '<<xmin<<' '<<ymin<<'\n';
    g.close();
    return 0;
}