Cod sursa(job #1127066)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 27 februarie 2014 11:01:37
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <cstring>
#include <queue>

using namespace std;

int N, M, i, j;

pair<int, int> R_POS;
pair<int, int> J_POS;

int MAP[500][500];

int MAP_R[500][500];

int MAP_J[500][500];

int DIR_X[] = {0, 0, 1, -1, 1, -1, 1, -1};

int DIR_Y[] = {1, -1, 0, 0, 1, 1, -1, -1};

void show_map(int MAP[][500])
{

    for(i=0;i<=N+1;++i)
    {

        for(j=0;j<=M+1;++j)
            cout<<MAP[i][j];
        cout<<"\n";
    }
}

void show_dmin(int DMIN[][500])
{

    for(i=1;i<=N;++i)
    {

        for(j=1;j<=M;++j)
            cout<<(DMIN[i][j] == 99999 ? -1 : DMIN[i][j])<<" ";
        cout<<"\n";
    }

}

void border()
{

    for(i=0;i<=N+1;++i)
        MAP[i][M+1] = 0, MAP[i][0] = 0;

    for(i=0;i<=M+1;++i)
        MAP[N+1][i] = 0, MAP[0][i] = 0;

}

void lee(int MAP[][500], int DMIN[][500], pair<int, int> S_POS)
{

    queue<pair<int, int> > Q;

    Q.push(S_POS);
    DMIN[S_POS.first][S_POS.second] = 0;

    while(!Q.empty())
    {
        pair<int, int> now = Q.front();

        // Try to move in all directions
        for(i=0;i<8;++i)
        {
            if(MAP[now.first + DIR_X[i]][now.second + DIR_Y[i]] == 1 && DMIN[now.first][now.second] + 1 < DMIN[now.first + DIR_X[i]][now.second + DIR_Y[i]])
            {

                DMIN[now.first + DIR_X[i]][now.second + DIR_Y[i]] = DMIN[now.first][now.second] + 1;

                Q.push(make_pair(now.first + DIR_X[i], now.second + DIR_Y[i]));

            }

        }

        Q.pop();
    }

}

int main()
{

    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    scanf("%d %d", &N, &M);

    int DMINR[500][500], DMINJ[500][500];

    for(i=1;i<=N;++i)
    {
        scanf("\n");
        for(j=1;j<=M;++j)
        {

            char c;

            scanf("%c", &c);

            MAP[i][j] = 0;  //BLOCKED
            DMINR[i][j] = 99999;
            DMINJ[i][j] = 99999;

            if(c == 'R')
                R_POS = make_pair(i, j);
            else if(c == 'J')
                J_POS = make_pair(i, j);
            else if(c == ' ')
                MAP[i][j] = 1;

        }
    }

    border();
//    copy(begin(MAP), end(MAP), begin(MAP_R));

    memcpy(&MAP_R, &MAP, sizeof(MAP));
    memcpy(&MAP_J, &MAP, sizeof(MAP));

    lee(MAP_R, DMINR, R_POS);
    lee(MAP_J, DMINJ, J_POS);

    //show_dmin(DMINR);
    //cout<<"\n";
    //show_dmin(DMINJ);

    pair<int, int> REZ = make_pair(0, 0);

    for(i=1;i<=N;++i)
        for(j=1;j<=M;++j)
            if(DMINR[i][j] == DMINJ[i][j] && DMINR[i][j] != 99999 && (REZ == make_pair(0, 0) || DMINR[i][j] < DMINR[REZ.first][REZ.second]))
                REZ = make_pair(i, j);

    cout<<(DMINR[REZ.first][REZ.second] + 1)<<" "<<REZ.first<<" "<<REZ.second<<"\n";

    return 0;
}