Cod sursa(job #2194580)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 13 aprilie 2018 19:39:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <cstdio>
#include <queue>
using namespace std;

queue <pair<int,int> >Q;
int t[260][260];
int je[260][260];
int vi[8]={-1,-1,-1,0,1,1,1,0};
int vj[8]={-1,0,1,1,1,0,-1,-1};


int n,m;
void bordare()
{
    t[0][0]=-1;
    t[0][m+1]=-1;
    t[n+1][0]=-1;
    t[n+1][m+1]=-1;
    je[0][0]=-1;
    je[0][m+1]=-1;
    je[n+1][0]=-1;
    je[n+1][m+1]=-1;
    for(int i=1; i<=n; i++)
    {
        t[i][0]=-1;
        t[i][m+1]=-1;
        je[i][0]=-1;
        je[i][m+1]=-1;
    }
    for(int i=1; i<=m; i++)
    {
        t[0][i]=-1;
        t[n+1][i]=-1;
        je[0][i]=-1;
        je[n+1][i]=-1;
    }
}

int lee(int a[260][260], int pi, int pj)
{
    a[pi][pj]=1;
    Q.push(make_pair(pi, pj));
    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        Q.pop();
        for(int v=0; v<8; v++)
        {
            int iv=i+vi[v];
            int jv=j+vj[v];
            if(a[iv][jv] == 0)
            {
                Q.push(make_pair(iv,jv));
                a[iv][jv]=a[i][j]+1;
            }
        }
    }
}


char aa[300];
int main()
{
    FILE *f=fopen("rj.in", "r");
    freopen("rj.out", "w", stdout);
    char x;

    fscanf(f, "%d %d\n", &n, &m);
    bordare();
    int  pi, pj, si, sj;
    for(int i=1; i<=n; i++)
    {
        fgets(aa, 300, f);
        for(int j=0; j<m;j++){
            if(aa[j]=='X')
            {
                t[i][j+1]=-1;
                je[i][j+1]=-1;
            }
            if(aa[j]=='J')
            {
                pi=i;
                pj=j+1;
            }
            if(aa[j]=='R')
            {
                si=i;
                sj=j+1;
            }
        }
    }

    lee(je,pi,pj);
    lee(t,si,sj);
    int vmin=n*m;
    int x1, y1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(t[i][j]==je[i][j] && t[i][j]<vmin && t[i][j]>0)
            {
                vmin=t[i][j];
                x1=i;
                y1=j;
            }
    printf("%d %d %d\n",vmin,x1,y1);
    return 0;
}