Cod sursa(job #1596920)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 11 februarie 2016 15:14:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int a[105][105],mat[105][105],L,C,xr,yr,xj,yj;
short dx[] = {-1,-1,-1, 0, 1, 1, 1, 0};
short dy[] = {-1, 0, 1, 1, 1, 0,-1,-1};
struct coord
{
    int x,y;
};
coord q[10000];
int main()
{
    int i,j;
    char s[110];
    f>>L>>C;
    f.get();
    for(i=1; i<=L; i++)
    {
        f.getline(s,110);
        for(j=0; j<C; j++)

            if(s[j]==' ')   a[i][j+1] = 0;
            else if(s[j]=='X')  a[i][j+1] = -1;
                else if(s[j]=='R')  {   xr = i; yr = j+1; }
                    else    {   xj = i; yj = j+1;   }
    }
    for(i=1; i<=L; i++)
        for(j=1; j<=C; j++)
            mat[i][j] = a[i][j];
    int n,m;
    n = L + 1;
    m = C + 1;
    for(i=0; i<=n; i++)
        mat[i][0] = mat[i][m] = a[i][0] = a[i][m] = -1;
    for(i=0; i<=m; i++)
        mat[0][i] = mat[n][i] = a[0][i] = a[n][i] = -1;
    int pr,ul,x,y,k;
    pr = ul = 0;
    a[xr][yr] = 1;
    q[ul].x = xr;
    q[ul].y = yr;
    while(pr<=ul)
    {
        i = q[pr].x;
        j = q[pr].y;
        pr++;
        for(k=0; k<8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];

            if(a[x][y] == 0)
            {
                ul++;
                q[ul].x = x;
                q[ul].y = y;
                a[x][y] = a[i][j] + 1;
            }
        }
    }
    pr = ul = 0;
    mat[xj][yj] = 1;
    q[ul].x = xj;
    q[ul].y = yj;
    while(pr<=ul)
    {
        i = q[pr].x;
        j = q[pr].y;
        pr++;
        for(k=0; k<8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if(mat[x][y] == 0)
            {
                ul++;
                q[ul].x = x;
                q[ul].y = y;
                mat[x][y] = mat[i][j] + 1;
            }
        }
    }
    int lin=0,col=0,tmin=1000000;
    for(i=1; i<=L; i++)
        for(j=1; j<=C; j++)
        {
            if(a[i][j] == mat[i][j] && a[i][j] > 1)
            {
                if(a[i][j] < tmin)
                {
                    tmin = a[i][j];
                    lin = i;
                    col = j;
                }
            }
        }
    g<<tmin<<" "<<lin<<" "<<col<<"\n";
    return 0;
}