Cod sursa(job #2094451)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 25 decembrie 2017 21:36:35
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
using namespace std;

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

#define x first
#define y second

const int NMAX = 100, INF = 2e9;

int n, m;
int a[2][NMAX + 2][NMAX + 2];
string str;

queue<pair<int, int>> q[2];
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1},
    dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

void bordare();

void bfs(bool arg)
{
    while(!q[arg].empty())
    {
        pair<int, int> fr = q[arg].front();

        for(int d = 0; d < 8; d++)
        {
            pair<int, int> vecin(fr.x + dx[d], fr.y + dy[d]);
            if(!a[arg][vecin.x][vecin.y])
            {
                a[arg][vecin.x][vecin.y] = a[arg][fr.x][fr.y] + 1;
                q[arg].push(vecin);
            }
        }

        q[arg].pop();
    }
}

int main()
{
    in >> n >> m; in.ignore();
    for(int i = 1; i <= n; i++)
    {
        getline(in, str);
        for(int j = 1; j <= m; j++)
            if(str[j - 1] == 'R' || str[j - 1] == 'J')
            {
                bool ind = (str[j - 1] == 'J');
                q[ind].push({i, j});
                a[ind][i][j] = 1;
            }
            else if(str[j - 1] == 'X')
                a[0][i][j] = a[1][i][j] = -1;
    }
    bordare();

    bfs(0); bfs(1);

    int ans = INF, x, y;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(a[0][i][j] == a[1][i][j] && a[0][i][j] > 1)
            if(a[0][i][j] < ans)
            {
                ans = a[0][i][j];
                x = i;
                y = j;
            }

    out << ans << ' ' << x << ' ' << y << '\n';
    return 0;
}

void bordare()
{
    for(int i = 0; i <= n + 1; i++)
    {
        a[0][i][0] = a[0][i][m + 1] = -1;
        a[1][i][0] = a[1][i][m + 1] = -1;
    }
    for(int j = 0; j <= m + 1; j++)
    {
        a[0][0][j] = a[0][n + 1][j] = -1;
        a[1][0][j] = a[1][n + 1][j] = -1;
    }
}