Cod sursa(job #2305419)

Utilizator ioanaa_ghGhiorghi Ioana-Cristina ioanaa_gh Data 20 decembrie 2018 10:21:02
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <bits/stdc++.h>
#define inf 1000007
using namespace std;

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

char s[105];
int b[105][105], c[105][105], n, m, sx, sy, fx, fy;
int dx[] = {1, -1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
queue < pair < int, int > > Q;

void Citire()
{
    int i, j;
    fin >> n >> m;
    for(i = 0; i <= n; i++)
    {
        fin.getline(s + 1, 105);
        for(j = 1; j <= m; j++)
        {
            if(s[j] == ' ')
            {
                b[i][j] = inf;
                c[i][j] = inf;
            }
            else if(s[j] == 'X')
            {
                b[i][j] = -1;
                c[i][j] = -1;
            }
            else if(s[j] == 'R')
            {
                b[i][j] = 1;
                c[i][j] = inf;
                sx = i;
                sy = j;
            }
            else if(s[j] == 'J')
            {
                b[i][j] = inf;
                c[i][j] = 1;
                fx = i;
                fy = j;
            }
        }
    }
}
void Bordare()
{
    int i;
    for(i = 0; i <= n + 1; i++)
        b[i][0] = b[i][m + 1] = c[i][0] = c[i][m + 1] = -1;
    for(i = 0; i <= m + 1; i++)
        b[0][i] = b[n + 1][i] = c[i][0] = c[i][m + 1] = -1;
}
void Lee()
{
    int k, ok, i, j, x, y, mn = inf + 1;
    Q.push({sx, sy});
    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for(k = 0; k < 8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if(b[x][y] != -1 && b[x][y] > b[i][j] + 1)
            {
                b[x][y] = b[i][j] + 1;
                Q.push({x, y});
            }
        }
    }
    Q.push({fx, fy});
    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for(k = 0; k < 8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if(c[x][y] != -1 && c[x][y] > c[i][j] + 1)
            {
                c[x][y] = c[i][j] + 1;
                Q.push({x, y});
            }
        }
    }
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m ; j++)
            if(b[i][j] != -1 && b[i][j] == c[i][j] && mn > b[i][j])
        {
            mn = b[i][j];
            x = i;
            y = j;
        }
    }
    fout << b[x][y] << " " << x << " " << y << "\n";
    fout.close();
}
int main()
{
    Citire();
    Bordare();
    Lee();
    return 0;
}