Cod sursa(job #379245)

Utilizator freak93Adrian Budau freak93 Data 31 decembrie 2009 11:18:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const char iname[]="rj.in";
const char oname[]="rj.out";
const int maxn=107;
const int INF=(1<<31)-1;

char s[maxn];

int x1,y1,x2,y2,i,j,n,m,mint,disr[maxn][maxn],disj[maxn][maxn];

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

queue<pair<int,int> > Q;

int main()
{
    freopen(iname,"r",stdin);
    freopen(oname,"w",stdout);

    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;++i)
    {
        fgets(s,sizeof(s),stdin);
        for(j=0;j<m;++j)
            if(s[j]=='R')
                x1=i,y1=j+1,disr[i][j+1]=INF,disj[i][j+1]=INF;
            else
                if(s[j]=='J')
                    x2=i,y2=j+1,disr[i][j+1]=INF,disj[i][j+1]=INF;
                else
                    if(s[j]=='X')
                        disr[i][j+1]=disj[i][j+1]=-1;
                    else
                        disr[i][j+1]=disj[i][j+1]=INF;
        disr[i][0]=disr[i][m+1]=disj[i][0]=disj[i][m+1]=-1;
    }
    for(i=0;i<=m+1;++i)
        disr[0][i]=disr[n+1][i]=disj[0][i]=disj[n+1][i]=-1;

    Q.push(make_pair(x1,y1));
    disr[x1][y1]=1;
    while(!Q.empty())
    {
        x=Q.front().first;
        y=Q.front().second;
        Q.pop();
        for(i=0;i<8;++i)
            if(disr[x+dx[i]][y+dy[i]]>disr[x][y]+1)
                disr[x+dx[i]][y+dy[i]]=disr[x][y]+1,Q.push(make_pair(x+dx[i],y+dy[i]));
    }

    Q.push(make_pair(x2,y2));
    disj[x2][y2]=1;
    while(!Q.empty())
    {
        x=Q.front().first;
        y=Q.front().second;
        Q.pop();
        for(i=0;i<8;++i)
            if(disj[x+dx[i]][y+dy[i]]>disj[x][y]+1)
                disj[x+dx[i]][y+dy[i]]=disj[x][y]+1,Q.push(make_pair(x+dx[i],y+dy[i]));
    }


    mint=INF;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(disr[i][j]==disj[i][j]&&disr[i][j]>0&&disr[i][j]<mint)
                mint=disr[i][j],x=i,y=j;

    printf("%d %d %d\n",mint,x,y);

    fclose(stdin);
    fclose(stdout);

    return 0;
}