Cod sursa(job #1133809)

Utilizator uagamagaMatei Rogoz uagamaga Data 5 martie 2014 17:33:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int n,m;
int M[105][105];
int rx,ry,jx,jy;
queue < pair<int,int> > C;


void BF(int x,int y,int dist[][105])
{
    pair <int,int> vec;
    C.push(make_pair(x,y));
    dist[x][y] = 1;

    while(!C.empty())
    {
        vec = C.front();

        if(vec.first>1 && !M[vec.first-1][vec.second])
        {
            if(!dist[vec.first-1][vec.second])
            {
                dist[vec.first-1][vec.second] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first-1,vec.second));
            }
        }
        if(!M[vec.first][vec.second+1] && vec.second<m)
        {
            if(!dist[vec.first][vec.second+1])
            {
                dist[vec.first][vec.second+1] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first,vec.second+1));
            }
        }
        if(!M[vec.first+1][vec.second] && vec.first<n)
        {
            if(!dist[vec.first+1][vec.second])
            {
                dist[vec.first+1][vec.second] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first+1,vec.second));
            }
        }
        if(!M[vec.first][vec.second-1] && vec.second>1)
        {
            if(!dist[vec.first][vec.second-1])
            {
                dist[vec.first][vec.second-1] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first,vec.second-1));
            }
        }


        if(!M[vec.first-1][vec.second-1] && vec.first>1 && vec.second>1)
        {
            if(!dist[vec.first-1][vec.second-1])
            {
                dist[vec.first-1][vec.second-1] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first-1,vec.second-1));
            }
        }
        if(!M[vec.first+1][vec.second+1] && vec.first<n && vec.second<m)
        {
            if(!dist[vec.first+1][vec.second+1])
            {
                dist[vec.first+1][vec.second+1] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first+1,vec.second+1));
            }
        }
        if(!M[vec.first+1][vec.second-1] && vec.first<n && vec.second>1)
        {
            if(!dist[vec.first+1][vec.second-1])
            {
                dist[vec.first+1][vec.second-1] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first+1,vec.second-1));
            }
        }
        if(!M[vec.first-1][vec.second+1] && vec.first>1 && vec.second<m)
        {
            if(!dist[vec.first-1][vec.second+1])
            {
                dist[vec.first-1][vec.second+1] = dist[vec.first][vec.second] + 1;
                C.push(make_pair(vec.first-1,vec.second+1));
            }
        }
        C.pop();
    }
}
int main()
{
    int i,j,rendX=0,rendY=0;
    int distR[105][105]={0},distJ[105][105]={0};
    string space = " ";
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;++i)
    {
        string line;
        getline(fin,line);
        for(j=0;j<m-line.length();++j) line += space;
        for(j=0;j<line.length();++j)
        {
            if(line[j]==' '){M[i][j+1]=0;}
            if(line[j]=='X'){M[i][j+1]=-1;}
            if(line[j]=='R'){M[i][j+1]=1;rx=i;ry=j+1;}
            if(line[j]=='J'){M[i][j+1]=2;jx=i;jy=j+1;}
        }
    }

    BF(rx,ry,distR);
    BF(jx,jy,distJ);

    int min = m*n;
    int retcol = m;

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(distR[i][j]!=0 && distR[i][j]==distJ[i][j] && distR[i][j]<=min)
                min = distR[i][j];


    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(distR[i][j]!=0 && distR[i][j]==min)
                if(j<=retcol)
                {
                    rendX = i;
                    rendY = j;
                    retcol = j;
                }


    fout<<min<<" "<<rendX<<" "<<rendY;

    return 0;
}