Cod sursa(job #1714187)

Utilizator zeeboBuzatu Vlad zeebo Data 7 iunie 2016 18:38:52
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

ifstream f ("rj.in");
ofstream g ("rj.out");

bool limite (int x, int y, int n, int m) {
    if ( x >= 1 && x <= n && y >= 1 && y <= m)
        return true;
    return false;
}

const int dx[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
const int dy[8] = { 0, 0, 1, -1,1, 1, -1, -1};

int n,m, x1, x2, y1, y2, pozi, pozj;
int romeo[101][101], julieta[101][101];

struct structura{
    int x,y;
};

queue <structura> Q;

char str[101];

int main () {

    f>>n>>m;
    f.getline(str,101);

    for (int i = 1; i <= n; i++)
    {
        f.getline(str,101);
        for (int j = 0; j < strlen(str); j++)
        {
            if (str[j] == ' ')
                romeo[i][j+1] = julieta[i][j+1] = 999;
            else
            if (str[j] == 'X')
                romeo[i][j+1] = julieta[i][j+1] = -1;
            else
            if (str[j] == 'R')
                x1 = i, y1 = j+1, romeo[x1][y1] = 0;
            else
            if (str[j] == 'J')
                x2 = i, y2 = j+1, julieta[x2][y2] = 0;
        }

        if (strlen(str) < m)
            for (int j = strlen(str) + 1; j <= m; j++)
                romeo[i][j] = julieta[i][j] = 999;
    }

// R

    structura st;
    st.x = x1;
    st.y = y1;
    Q.push(st);

    while(!Q.empty()){
        for (int i = 0; i <= 7; i++)
            if (romeo[Q.front().x + dx[i]][Q.front().y+dy[i]] == 999 && limite (Q.front().x + dx[i], Q.front().y + dy[i], n, m)){
                st.x = Q.front().x + dx[i];
                st.y = Q.front().y + dy[i];
                romeo[st.x][st.y] = romeo[Q.front().x][Q.front().y] + 1;
                Q.push(st);
            }
            Q.pop();
    }

// J

    st.x = x2;
    st.y = y2;
    Q.push(st);

    while(!Q.empty()){
        for (int i = 0; i <= 7; i++)
            if (julieta[Q.front().x + dx[i]][Q.front().y+dy[i]] == 999 && limite (Q.front().x + dx[i], Q.front().y + dy[i], n, m)){
                st.x = Q.front().x + dx[i];
                st.y = Q.front().y + dy[i];
                julieta[st.x][st.y] = julieta[Q.front().x][Q.front().y] + 1;
                Q.push(st);
            }
            Q.pop();
    }

    int minim = 999;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (romeo[i][j] == julieta[i][j] && romeo[i][j] < minim && romeo[i][j] > 0){
                minim = romeo[i][j];
                pozi = i;
                pozj = j;
            }

    g << minim + 1 << " " << pozi << " " << pozj;

    return 0;
}