Cod sursa(job #1373012)

Utilizator bogdanel32Bogdan bogdanel32 Data 4 martie 2015 16:20:25
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <cstdio>

#include <queue>

using namespace std;

struct POINT
{
    int x,y;
};

int r[200][200],j[200][200];

queue <POINT> q;

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    short int x1,x2,y1,y2,n,m,i,c,k,minim;
    char x;
    scanf("%hd%hd",&n,&m);
    for(i=1;i<=n;++i)
        {
        scanf("\n");
        for(c=1;c<=m;++c)
            {
                scanf("%c",&x);
                if(x==' ') j[i][c]=r[i][c]=0;
                    else if(x=='X') j[i][c]=r[i][c]=-1;
                        else if(x=='R') {
                                        x1=i;
                                        y1=c;
                                        j[i][c]=0;
                                        }
                                else if(x=='J')
                                        {
                                        x2=i;
                                        y2=c;
                                        r[i][c]=0;
                                        }
            }
        }
    for(i=1;i<=n;++i)
        {
            r[i][0]=j[i][0]=-1 ;
            r[i][n+1]=j[i][n+1]=-1;
        }
    for(c=1;c<=m;c++)
        {
            r[0][c]=j[0][c]=-1;
            r[n+1][c]=j[n+1][c]=-1;
        }
    r[x1][y1]=0;
    POINT temp,tempnew;
    temp.x=x1;temp.y=y1;
    q.push(temp);
    while(!q.empty())
    {
        temp=q.front();
        for(k=0;k<4;++k)
            {
                tempnew.x=temp.x+dx[k];
                tempnew.y=temp.y+dy[k];
                if(r[tempnew.x][tempnew.y]==0)
                        {
                        r[tempnew.x][tempnew.y]=r[temp.x][temp.y]+1;
                        q.push(tempnew);
                        }
            }
        q.pop();
    }
    j[x2][y2]=0;
    temp.x=x2;temp.y=y2;
    q.push(temp);
    while(!q.empty())
    {
        temp=q.front();
        for(k=0;k<4;++k)
            {
                tempnew.x=temp.x+dx[k];
                tempnew.y=temp.y+dy[k];
                if(j[tempnew.x][tempnew.y]==0)
                    {
                    j[tempnew.x][tempnew.y]=j[temp.x][temp.y]+1;
                    q.push(tempnew);
                    }
            }
        q.pop();
    }
    minim=200;
    for(i=1;i<=n;i++)
        for(c=1;c<=m;c++)
            {
            if(j[i][c]==r[i][c]&&r[i][c]!=-1&&r[i][c]!=0) {
                                if(minim>j[i][c]) minim=j[i][c];
                                }
            }
    printf("%hd ",minim);
    for(i=1;i<=n;i++)
        for(c=1;c<=m;c++)
            {
            if(j[i][c]==minim && minim==r[i][c]) {
                                                    printf("%hd %hd\n",i,c);
                                                    break;
                                                    }
            }
    return 0;
}