Cod sursa(job #969982)

Utilizator addy01adrian dumitrache addy01 Data 5 iulie 2013 20:21:27
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;


struct om
{
    int x,y;
};

queue <om> Q1,Q2;
int dl[]={-1,-1,0,1,1,1,0,-1},dc[]={0,1,1,1,0,-1,-1,-1};
int a[105][105],n,m,b[105][105];
bool viz[105][105];

bool ok(int x , int y)
{
    return ( ( x >= 1 ) && ( x <= n ) && ( y >= 1 ) && ( y <= m ) && a[x][y] != -1 );
}

void BFS(queue <om> Q, int a[105][105])
{
    memset(viz,0,sizeof(viz));
    while(!Q.empty())
    {
        om x;
        x=Q.front();
        Q.pop();
        for(int k=0;k<8;k++)
        {
            om y;
            y.x=x.x+dl[k];
            y.y=x.y+dc[k];
            if( ok( y.x , y.y ) && !viz[y.x][y.y] )
            {
                viz[y.x][y.y]=1;
                if( a[y.x][y.y] != -2 || a[ x.x ][ x.y ]+1 < a[ y.x ][ y.y ]  )
                   {
                   //if( a[ x.x ][ x.y ]+1 < a[ y.x ][ y.y ] )
                        {
                            a[ y.x ][ y.y ] = a[ x.x ][ x.y ] + 1;
                            Q.push(y);
                        }
                    }
                    else
                    {
                        a[ y.x ][ y.y ] = a[ x.x ][ x.y ] + 1;
                        Q.push(y);
                    }
            }

        }
    }
}


int main()
{
    ifstream in("rj.in");
    ofstream out("rj.out");

    int i,j;
    char c;
    in>>n>>m;
    char s[105];
    for(i=1;i<=n;i++)
        {
            in.get();
            in.get(s+1,105);
            for(j=1;j<=m;j++)
            {
                c=s[j];
                if(c=='R')
                        {
                            a[i][j]=0;
                            om x;
                            x.x=i;
                            x.y=j;
                            Q1.push(x);
                            b[i][j]=-1;
                        }
                    else
                        if(c=='J')
                    {
                            b[i][j]=0;
                            om x;
                            x.x=i;
                            x.y=j;
                            Q2.push(x);
                            a[i][j]=-1;

                    }
                        else
                            if(c=='X')
                                a[i][j]=-1,b[i][j]=-1;
                            else
                                a[i][j]=-2,b[i][j]=-2;
            }
        }

    for(i=0;i<=n+1;i++)
        a[i][0]=-1,a[i][m+1]=-1;

    for(i=0;i<=m+1;i++)
        a[0][i]=-1,a[n+1][i]=-1;


    for(i=0;i<=n+1;i++)
        b[i][0]=-1,b[i][m+1]=-1;

    for(i=0;i<=m+1;i++)
        b[0][i]=-1,b[n+1][i]=-1;


    BFS(Q1,a);
    BFS(Q2,b);
int tmin=1<<30,xmin,ymin;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if( a[i][j] == b[i][j] && a[i][j] != -1 && a[i][j] != -2 && a[i][j] < tmin )
                {
                    tmin=a[i][j]+1;
                    xmin=i;
                    ymin=j;
                }

out<<tmin<<" "<<xmin<<" "<<ymin<<"\n";


    return 0;
}