Cod sursa(job #1651374)

Utilizator mirunazMiruna Zavelca mirunaz Data 13 martie 2016 09:01:08
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
int i,j,n,m,linie[8]={0,0,1,1,1,-1,-1,-1},coloana[8]={1,-1,-1,0,1,-1,0,1},lin,col,mn,x,y;
int vr[102][102],vj[102][102];
char c,s[102];
struct sheldon{int l,c;};
sheldon frst,nxt,rom,jul;
queue <sheldon> q;
FILE *in, *out;
void lee_r()
{
    q.push(rom);
    vr[rom.l][rom.c]=1;
    while(!q.empty())
    {
        frst=q.front();
        q.pop();
        int h;
        for(h=0;h<8;h++)
        {
            nxt.l=frst.l+linie[h];
            nxt.c=frst.c+coloana[h];
            if(vr[nxt.l][nxt.c]==-1)
            {
                q.push(nxt);
                vr[nxt.l][nxt.c]=vr[frst.l][frst.c]+1;
            }
        }
    }
}
void lee_j()
{
    q.push(jul);
    vj[jul.l][jul.c]=1;
    while(!q.empty())
    {
        frst=q.front();
        q.pop();
        int t=vj[frst.l][frst.c];
        if(t==vr[frst.l][frst.c])
        {
            if(t<mn)
            {
                mn=t;
                x=frst.l;
                y=frst.c;
            }
            else if(t==mn)
            {
                if(frst.l<x)
                {
                    x=frst.l;
                    y=frst.c;
                }
                else if(frst.l==x && frst.c<y)
                    y=frst.c;
            }
        }
        int h;
        for(h=0;h<8;h++)
        {
            nxt.l=linie[h]+frst.l;
            nxt.c=coloana[h]+frst.c;
            if(vj[nxt.l][nxt.c]==-1)
            {
                q.push(nxt);
                vj[nxt.l][nxt.c]=vj[frst.l][frst.c]+1;
            }
        }
    }
}
int main ()
{
    in=fopen("rj.in","r");
    out=fopen("rj.out","w");
    fscanf(in,"%d %d%c",&n,&m,&c);
    mn=m*n;
    for(i=1;i<=n;i++)
    {
        fgets(s,102,in);
        for(j=1;j<=m;j++)
        {
            c=s[j-1];
            if(c!='X')
            {
                vr[i][j]=-1;
                vj[i][j]=-1;
                if(c=='R')
                {
                    rom.l=i;
                    rom.c=j;
                }
                else if(c=='J')
                {
                    jul.l=i;
                    jul.c=j;
                }
            }
        }
    }
    lee_r();
    lee_j();
    fprintf(out,"%d %d %d\n",mn,x,y);
    return 0;
}