Cod sursa(job #1170487)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 13 aprilie 2014 18:16:25
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <queue>

using namespace std;

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

int n,m;
char c[300];
queue<pair<int, int> > Q;
const int di[] = { 1, 0, -1, -1, -1, 0, 1,1  };
const int dj[] = { 1, 1, 1, 0, -1,-1,-1,0 };
int a[101][101];
int ro[101][101];
int ju[101][101];

bool inside(int i, int j)
{
    return i<=n && j<=m && i>=1 && j >= 1;
}


int main()
{
    fin>>n>>m;
    fin.getline(c,30);
    pair<int, int> romeo, julieta;
    for(int i=1;i<=n;i++)
    {
        fin.getline(c,300);
        for(int j=1;j<=m;j++)
            if(c[j-1] == 'X')
            {
                a[i][j]  = -1;
            }
            else if(c[j-1] == 'R')
            {
                romeo = make_pair(i,j);

            }
            else if(c[j-1] == 'J')
            {

                julieta = make_pair(i,j);
            }
    }

    Q.push(romeo);
    ro[romeo.first][romeo.second] = 1;
    while(!Q.empty())
    {
        int i = Q.front().first;
        int j = Q.front().second;
        for(int k=0;k<8;k++)
        {
            int inou = i + di[k];
            int jnou = j + dj[k];
            if( !a[inou][jnou] && !ro[inou][jnou])
            {
                Q.push(make_pair(inou, jnou) );
                ro[inou][jnou] = ro[i][j] + 1;
            }
        }
        Q.pop();
    }


    Q.push(julieta);
    ju[julieta.first][julieta.second] = 1;
    while(!Q.empty())
    {
        int i = Q.front().first;
        int j = Q.front().second;
        for(int k=0;k<8;k++)
        {
            int inou = i + di[k];
            int jnou = j + dj[k];
            if( !a[inou][jnou] && !ju[inou][jnou])
            {
                Q.push(make_pair(inou, jnou) );
                ju[inou][jnou] = ju[i][j] + 1;
            }
        }
        Q.pop();
    }
    int val_min = 0x3f3f3f3f;
    pair<int, int> sol;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ro[i][j] == ju[i][j] && ro[i][j] && ro[i][j] < val_min)
            {
                sol = make_pair(i,j);

                val_min = ro[i][j];
            }
    fout<<val_min<<' '<<sol.first<<' '<<sol.second;
    fin.close();
    return 0;
}