Cod sursa(job #1127229)

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

using namespace std;

const int xd[] = {1, 0, 0, -1, 1, 1, -1, -1};

const int yd[] = {0, 1, -1, 0, 1, -1, -1, 1};

int main()
{

    int N, M, i, j, sol, harta[105][105], hartaR[105][105], hartaJ[105][105];

    char c;

    pair<int, int> r_pos, j_pos, now;

    freopen("rj.in", "r", stdin);

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

    for(i=1;i<=N;++i)
    {
        //scanf("\n");
 cin.get();
        for(j=1;j<=M;++j)
        {
            //scanf("%c", &c);
 cin.get(c);
            if(c == ' ')
                harta[i][j] = 0;
            else if(c == 'X')
                harta[i][j] = 1;
            else if(c == 'R')
                r_pos = make_pair(i, j);
            else if(c == 'J')
                j_pos = make_pair(i, j);

        }

    }

    fclose(stdin);

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

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

    hartaR[r_pos.first][r_pos.second] = 1;
    hartaJ[j_pos.first][j_pos.second] = 1;

    queue<pair<int, int> > QR;
    queue<pair<int, int> > QJ;

    QR.push(r_pos);
    QJ.push(j_pos);

    while(!QR.empty() || !QJ.empty())
    {
        now = QR.front();

        for(i=0;i<8;++i)
            if(!harta[now.first+xd[i]][now.second+yd[i]] && !hartaR[now.first+xd[i]][now.second+yd[i]])
            {
                QR.push(make_pair(now.first+xd[i], now.second+yd[i]));
                hartaR[now.first+xd[i]][now.second+yd[i]] = hartaR[now.first][now.second] + 1;
            }

        QR.pop();

        now = QJ.front();

        for(i=0;i<8;++i)
            if(!harta[now.first+xd[i]][now.second+yd[i]] && !hartaJ[now.first+xd[i]][now.second+yd[i]])
            {
                QJ.push(make_pair(now.first+xd[i], now.second+yd[i]));
                hartaJ[now.first+xd[i]][now.second+yd[i]] = hartaJ[now.first][now.second] + 1;
            }

        QJ.pop();
    }

    sol = 10005;

    int sX=0, sY=0;

    for(j=1;j<=N;++j)
        for(i=1;i<=M;++i)
            if(hartaR[i][j] == hartaJ[i][j] && hartaR[i][j] && hartaJ[i][j] && sol > hartaR[i][j])
                    sol = hartaR[i][j], sX = i, sY = j;

    freopen("rj.out", "w", stdout);

    cout<<sol<<" "<<sX<<" "<<sY<<"\n";

    fclose(stdout);

    return 0;

}