Cod sursa(job #981351)

Utilizator thewildnathNathan Wildenberg thewildnath Data 6 august 2013 19:51:24
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.97 kb
#include<stdio.h>
#include<stack>
using namespace std;

typedef struct punct
{
    char x,y;
}punct;

char v[110][110];
int a[110][110],b[110][110];
int n,m,nr,x,y,k,sol=2000000000,solx,soly,i=1,j;
punct aux;
//stack <punct> st;

punct st[10004];

void lee1()
{
    st[++j]=aux;
    a[aux.x][aux.y]=1;
    while(i<=j)
    {
        x=st[i].x;
        y=st[i].y;
        k=a[x][y];
        ++i;
        if(k>=sol-1)
            continue;
        if(x>0&&v[x-1][y]==' '&&(a[x-1][y]==0||a[x-1][y]>k+1))
        {
            a[x-1][y]=k+1;
            aux.x=x-1;
            aux.y=y;
            st[++j]=aux;
        }
        if(y>0&&v[x][y-1]==' '&&(a[x][y-1]==0||a[x][y-1]>k+1))
        {
            a[x][y-1]=k+1;
            aux.x=x;
            aux.y=y-1;
            st[++j]=aux;
        }
        if(x<n-1&&v[x+1][y]==' '&&(a[x+1][y]==0||a[x+1][y]>k+1))
        {
            a[x+1][y]=k+1;
            aux.x=x+1;
            aux.y=y;
            st[++j]=aux;
        }
        if(y<m-1&&v[x][y+1]==' '&&(a[x][y+1]==0||a[x][y+1]>k+1))
        {
            a[x][y+1]=k+1;
            aux.x=x;
            aux.y=y+1;
            st[++j]=aux;
        }
        ///////////////////////////
        if(x>0&&y>0&&v[x-1][y-1]==' '&&(a[x-1][y-1]==0||a[x-1][y-1]>k+1))
        {
            a[x-1][y-1]=k+1;
            aux.x=x-1;
            aux.y=y-1;
            st[++j]=aux;
        }
        if(x<n-1&&y>0&&v[x+1][y-1]==' '&&(a[x+1][y-1]==0||a[x+1][y-1]>k+1))
        {
            a[x+1][y-1]=k+1;
            aux.x=x+1;
            aux.y=y-1;
            st[++j]=aux;
        }
        if(x<n-1&&y<m-1&&v[x+1][y+1]==' '&&(a[x+1][y+1]==0||a[x+1][y+1]>k+1))
        {
            a[x+1][y+1]=k+1;
            aux.x=x+1;
            aux.y=y+1;
            st[++j]=aux;
        }
        if(x>0&&y<m-1&&v[x-1][y+1]==' '&&(a[x-1][y+1]==0||a[x-1][y+1]>k+1))
        {
            a[x-1][y+1]=k+1;
            aux.x=x-1;
            aux.y=y+1;
            st[++j]=aux;
        }
    }
}

void lee2()
{
    while(i<=j)
        ++i;
    st[++j]=aux;
    b[aux.x][aux.y]=1;
    while(i<=j)
    {
        x=st[i].x;
        y=st[i].y;
        k=b[x][y];
        ++i;
        if(k>=sol-1)
            continue;
        if(x>0&&v[x-1][y]==' '&&(b[x-1][y]==0||b[x-1][y]>k+1))
        {
            b[x-1][y]=k+1;
            aux.x=x-1;
            aux.y=y;
            st[++j]=aux;
        }
        if(y>0&&v[x][y-1]==' '&&(b[x][y-1]==0||b[x][y-1]>k+1))
        {
            b[x][y-1]=k+1;
            aux.x=x;
            aux.y=y-1;
            st[++j]=aux;
        }
        if(x<n-1&&v[x+1][y]==' '&&(b[x+1][y]==0||b[x+1][y]>k+1))
        {
            b[x+1][y]=k+1;
            aux.x=x+1;
            aux.y=y;
            st[++j]=aux;
        }
        if(y<m-1&&v[x][y+1]==' '&&(b[x][y+1]==0||b[x][y+1]>k+1))
        {
            b[x][y+1]=k+1;
            aux.x=x;
            aux.y=y+1;
            st[++j]=aux;
        }
        ///////////////////////////
        if(x>0&&y>0&&v[x-1][y-1]==' '&&(b[x-1][y-1]==0||b[x-1][y-1]>k+1))
        {
            b[x-1][y-1]=k+1;
            aux.x=x-1;
            aux.y=y-1;
            st[++j]=aux;
        }
        if(x<n-1&&y>0&&v[x+1][y-1]==' '&&(b[x+1][y-1]==0||b[x+1][y-1]>k+1))
        {
            b[x+1][y-1]=k+1;
            aux.x=x+1;
            aux.y=y-1;
            st[++j]=aux;
        }
        if(x<n-1&&y<m-1&&v[x+1][y+1]==' '&&(b[x+1][y+1]==0||b[x+1][y+1]>k+1))
        {
            b[x+1][y+1]=k+1;
            aux.x=x+1;
            aux.y=y+1;
            st[++j]=aux;
        }
        if(x>0&&y<m-1&&v[x-1][y+1]==' '&&(b[x-1][y+1]==0||b[x-1][y+1]>k+1))
        {
            b[x-1][y+1]=k+1;
            aux.x=x-1;
            aux.y=y+1;
            st[++j]=aux;
        }
    }
}

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int i,j;
    scanf("%d%d\n",&n,&m);
    for(i=0;i<n;++i)
        fgets(v[i],200,stdin);

    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            if(v[i][j]=='R'||v[i][j]=='J')
            {
                ++nr;
                aux.x=i;
                aux.y=j;
                if(v[i][j]=='R')
                    lee1();
                else
                    lee2();
                if(nr==2)
                {
                    i=n+1;
                    break;
                }
            }
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            if(a[i][j]==b[i][j]&&a[i][j]<sol&&a[i][j]>0)
            {
                sol=a[i][j];
                solx=i;
                soly=j;
            }
    /*for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
            printf("%2d ",a[i][j]);
        printf("\n");
    }
    printf("\n");printf("\n");
    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
            printf("%2d ",b[i][j]);
        printf("\n");
    }*/
    printf("%d %d %d\n",sol,solx+1,soly+1);
    return 0;
}