Cod sursa(job #1376094)

Utilizator taigi100Cazacu Robert taigi100 Data 5 martie 2015 15:57:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
/*
    Keep It Simple!
*/

#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("rj.in");
ofstream cout("rj.out");

#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int kMaxN = 105;

char mat[kMaxN][kMaxN];
int rmat[kMaxN][kMaxN],jmat[kMaxN][kMaxN];
int n,m;

struct loc {
    int x,y;
    loc(int a,int b) : x{a},y{b} {}
    loc() : x(0),y(0) {}
    }romeo,juliet,aux;
int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};

queue<loc> que;

void Lee(int arr[kMaxN][kMaxN],loc start)
{
    que.push(start);
    arr[start.x][start.y] = 1;
    while(!que.empty())
    {
        aux.x = que.front().x;
        aux.y = que.front().y;
        que.pop();

        for(int i=0; i<8; ++i)
        {
            int newx = aux.x + dx[i];
            int newy = aux.y + dy[i];
            if(mat[newx][newy] == ' ' && arr[newx][newy] == 0)
            {
                arr[newx][newy] = arr[aux.x][aux.y] + 1;
                que.push(loc(newx,newy));
            }
        }
    }
}

void Solve()
{
    cin >> n >> m; cin.get();
    for(int i=0;i<n;++i)
    {
        cin.getline(mat[i],kMaxN);
        for(int j=0;j<m;++j)
           {
                if(mat[i][j] == 'R') { romeo.x = i; romeo.y = j; }
                if(mat[i][j] == 'J') { juliet.x = i; juliet.y = j; }
           }
    }

    Lee(rmat,romeo);
    Lee(jmat,juliet);

    int tmin = 1<<30;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            if(mat[i][j] == ' ' && rmat[i][j] == jmat[i][j] && rmat[i][j] && rmat[i][j] < tmin)
                tmin = rmat[i][j],aux.x=i,aux.y=j;
        }
    cout << tmin << ' ' << aux.x+1 << ' ' << aux.y+1;
}

int main()
{
    Solve();
    return 0;
}