Cod sursa(job #1575800)

Utilizator armandpredaPreda Armand armandpreda Data 21 ianuarie 2016 21:10:56
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int LIM=105;
int n, m, rom[LIM][LIM], jul[LIM][LIM], xr, yr, xj, yj;
char s[LIM];
queue < pair <int, int> > q;
void bfs(int x, int y, int mat[][LIM])
{
    int dx[]={0, -1, -1, 0, 1, 1, 1, 0, -1}, dy[]={0, 0, 1, 1, 1, 0, -1, -1, -1};
    mat[x][y]=1;
    q.push({x, y});
    while(!q.empty())
    {
        x=q.front().first, y=q.front().second;
        q.pop();
        for(int i=1; i<=8; ++i)
            if(!mat[ x+dx[i] ][ y+dy[i] ])
            {
                mat[ x+dx[i] ][ y+dy[i] ]=mat[x][y]+1;
                q.push({x+dx[i], y+dy[i]});
            }
    }
}
void afis(int mat[][LIM])
{
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
            printf("%3d ", mat[i][j]);
        printf("\n");
    }
    printf("\n");
}
int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for(int i=1; i<=n; ++i)
    {
        gets(s+1);
        for(int j=1; j<=m; ++j)
        {
            if(s[j]=='R') xr=i, yr=j;
            if(s[j]=='J') xj=i, yj=j;
            if(s[j]=='X')
                rom[i][j]=jul[i][j]=-1;
        }
    }
    for(int i=0; i<=n+1; ++i)
        rom[i][0]=rom[i][m+1]=jul[i][0]=jul[i][m+1]=-1;
    for(int i=0; i<=m+1; ++i)
        rom[0][i]=rom[n+1][i]=jul[0][i]=jul[n+1][i]=-1;
    bfs(xr, yr, rom);
    bfs(xj, yj, jul);
    int ans=(1<<30), xmin, ymin;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            int cur=(1<<30);
            if(rom[i][j]==jul[i][j] and rom[i][j]>1)
                cur=rom[i][j];
            if(ans>cur)
            {
                ans=cur;
                xmin=i, ymin=j;
            }
        }
    //afis(rom);
    //afis(jul);
    printf("%d %d %d", ans, xmin, ymin);
    return 0;
}