Cod sursa(job #1134155)

Utilizator uagamagaMatei Rogoz uagamaga Data 6 martie 2014 09:19:29
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 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,M[105][105],rx,ry,jx,jy,directionsX[8] = {-1,0,1,0,-1,1,1,-1},directionsY[8] = {0,1,0,-1,-1,1,-1,1};
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();

        for(int k=0;k<8;++k)
        {
            int dirX = directionsX[k];
            int dirY = directionsY[k];
            if(!M[vec.first+dirX][vec.second+dirY])
            {
                if(!dist[vec.first+dirX][vec.second+dirY])
                {
                    dist[vec.first+dirX][vec.second+dirY] = dist[vec.first][vec.second] + 1;
                    C.push(make_pair(vec.first + dirX,vec.second + dirY));
                }
            }
        }
        C.pop();
    }
}
int main()
{
    int i,j,rendX=0,rendY=0,distR[105][105]={0},distJ[105][105]={0},min;
    string space = " ";
    fin>>n>>m;
    min = m*n;
    fin.get();

    for(j=0;j<=m+1;++j){M[0][j] = -1;M[n+1][j]=-1;}
    for(i=0;i<=n+1;++i){M[i][0] = -1;M[i][m+1]=-1;}

    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);

    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){
                rendX = i;
                rendY = j;
                min = distR[i][j];
            }

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

    return 0;
}