Cod sursa(job #1832715)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 20 decembrie 2016 19:43:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <queue>

using namespace std;

struct punct
{
    int x,y;
};

queue<punct> q;
char v[110][110];
int vaz[110][110],vaz1[110][110];
punct v1[10];

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int n,m,x1,y1,x2,y2,x,y,sol=1e9;
    scanf("%d%d\n",&n,&m);
    v1[0].x=-1;v1[1].x=-1;v1[1].y=1;v1[2].y=1;v1[3].x=1;v1[3].y=1;v1[4].x=1;v1[5].x=1;v1[5].y=-1;v1[6].y=-1;v1[7].x=-1;v1[7].y=-1;
    for(int i=1;i<=n;i++)
    {
        gets(v[i]+1);
        for(int j=1;j<=m;j++)
        {
            if(v[i][j]=='R') x1=i,y1=j;
            else if(v[i][j]=='J') x2=i,y2=j;
        }
    }
    vaz[x1][y1]=1;
    q.push({x1,y1});
    while(!q.empty())
    {
        x=q.front().x;
        y=q.front().y;
        q.pop();
        for(int i=0;i<8;i++)
            if(v[x+v1[i].x][y+v1[i].y]==' ' && vaz[x+v1[i].x][y+v1[i].y]==0)
            {
                vaz[x+v1[i].x][y+v1[i].y]=vaz[x][y]+1;
                q.push({x+v1[i].x,y+v1[i].y});
            }
    }
    vaz1[x2][y2]=1;
    q.push({x2,y2});
    while(!q.empty())
    {
        x=q.front().x;
        y=q.front().y;
        q.pop();
        for(int i=0;i<8;i++)
            if(v[x+v1[i].x][y+v1[i].y]==' ' && vaz1[x+v1[i].x][y+v1[i].y]==0)
            {
                vaz1[x+v1[i].x][y+v1[i].y]=vaz1[x][y]+1;
                q.push({x+v1[i].x,y+v1[i].y});
            }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(vaz[i][j]>0 && vaz[i][j]==vaz1[i][j]) if(vaz[i][j]<sol) {sol=vaz[i][j];x=i;y=j;}
    printf("%d %d %d",sol,x,y);
    return 0;
}