Cod sursa(job #1500238)

Utilizator denischiritachirita denis denischirita Data 11 octombrie 2015 17:19:51
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <queue>
using namespace std;
short int dr[103][103],dj[103][103];
int dx[]= {-1,-1,0,1,1,1,0,-1};
int dy[]= {0,1,1,1,0,-1,-1,-1};
struct R
{
    short int x,y;
};
struct J
{
    short int x,y;
};
queue<R>qr;
queue<J>qj;
char c[500];
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int n,m,i,j,lr,cr,lj,cj,p1,p2,min=(1<<30);
    char x;
    scanf("%d%d\n",&n,&m);
    for(i=1; i<=n; i++)
    {
        gets(c);
        for(j=1; j<=m; j++)
        {
            x=c[j-1];
            if(x=='R')
                lr=i,cr=j;
            else if(x=='J')
                lj=i,cj=j;
            else if(x=='X')
                dr[i][j]=-1,dj[i][j]=-1;
        }
    }
    for(j=0; j<=m+1; j++)
    {
        dr[0][j]=dr[n+1][j]=-1;
        dj[0][j]=dj[n+1][j]=-1;
    }
    for(i=0; i<=n+1; i++)
    {
        dr[i][0]=dr[i][m+1]=-1;
        dj[i][0]=dj[i][m+1]=-1;
    }
    dr[lr][cr]=1;
    dj[lj][cj]=1;
    R tata,newn;
    tata.x=lr;
    tata.y=cr;
    qr.push(tata);
    while(!qr.empty())
    {
        tata=qr.front();
        for(i=0; i<8; i++)
        {
            newn.x=tata.x+dx[i];
            newn.y=tata.y+dy[i];
            if(dr[newn.x][newn.y]==0)
            {
                qr.push(newn);
                dr[newn.x][newn.y]=dr[tata.x][tata.y]+1;
            }
        }
        qr.pop();
    }
    J tata2,newn2;
    tata2.x=lj;
    tata2.y=cj;
    qj.push(tata2);
    while(!qj.empty())
    {
        tata2=qj.front();
        for(i=0; i<8; i++)
        {
            newn2.x=tata2.x+dx[i];
            newn2.y=tata2.y+dy[i];
            if(dj[newn2.x][newn2.y]==0)
            {
                qj.push(newn2);
                dj[newn2.x][newn2.y]=dj[tata2.x][tata2.y]+1;
            }
        }
        qj.pop();
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        if(dr[i][j]==dj[i][j]&&dr[i][j]!=0&&dr[i][j]!=-1&&dr[i][j]!=1)
        if(dr[i][j]<min){
            min=dr[i][j];
            p1=i;
            p2=j;
        }
        printf("%d %d %d",min,p1,p2);
}