Cod sursa(job #413532)

Utilizator SpiderManSimoiu Robert SpiderMan Data 8 martie 2010 18:23:41
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
using namespace std;

#define MAX 100000
#define M 105
#define oo 0x3f3f3f3f

ifstream f("rj.in");
ofstream g("rj.out");

const int dx[]={-1,-1,0,1,1, 1 ,0,-1};
const int dy[]={ 0, 1,1,1,0,-1,-1,-1};

int st,dr,i,j,ii,jj,k,m,n,ct[M][M],cy[M][M],xx,yy,minim;
char s[M];

struct coada
{
    int I,J;
} R[MAX],J[MAX];

void citire()
{
    f>>n>>m;
    f.getline(s,2);
    for (i=1;i<=n;i++)
    {
        f.getline(s,110);
        for (j=0;j<m;j++)
        {
            if (s[j]=='X') ct[i][j+1]=cy[i][j+1]=-2;
            else if (s[j]=='J') ct[i][j+1]=-1;
            else if (s[j]=='R') cy[i][j+1]=-1;
            else ct[i][j+1]=cy[i][j+1]=0;
            if (ct[i][j+1]==-1)
            {
                J[0].I=i;
                J[0].J=j+1;
            }
            else if (cy[i][j+1]==-1)
            {
                R[0].I=i;
                R[0].J=j+1;
            }
        }
    }
}
void solve(int ct[][M],coada Q[])
{
    for (st=0,dr=1;st<dr;st++)
    {
        i=Q[st].I;
        j=Q[st].J;
        for (k=0;k<8;k++)
        {
            ii=i+dx[k];
            jj=j+dy[k];
            if (ct[ii][jj]==0 && ii>0 && ii<=n && jj>0 && jj<=m)
            {
                if (ct[i][j]==-1) ct[ii][jj]=ct[i][j]+2;
                else ct[ii][jj]=ct[i][j]+1;
                Q[dr].I=ii;
                Q[dr++].J=jj;
            }
        }
    }
}
void afis()
{
    minim=xx=yy=oo;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (ct[i][j]==cy[i][j] && ct[i][j]<=minim && ct[i][j]>0)
                if (ct[i][j]==minim)
                {
                    if (xx>i || xx==i && yy>j) xx=i,yy=j;
                }
                else minim=ct[i][j],xx=i,yy=j;

    g<<minim+1<<" "<<xx<<" "<<yy;
}
int main()
{
    citire();
    solve(ct,J);
    solve(cy,R);
    afis();
    return 0;
}