Cod sursa(job #2495961)

Utilizator NeganAlex Mihalcea Negan Data 20 noiembrie 2019 01:26:14
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>
#define oo 2000000000

using namespace std;
char s[255];
int a[255][255];
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
int n, m, d[155][155], d1[110][110], xr, yr, xj, yj;
inline bool Inside(int i, int j)
{
    return i <= n && i >= 1 && j <= m && j >= 1;
}


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

void Lee()
{
    int i, j, x, y, k;
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            d[i][j] = oo;
    d[xr][yr] = 1;
    queue< pair <int, int> >q;
    q.push(make_pair(xr, yr));
    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(Inside(x, y) && a[x][y] == 0 && d[x][y] > d[i][j] + 1)
            {
                d[x][y] = d[i][j] + 1;
                q.push(make_pair(x, y));
            }
        }
    }
}
void Lee2()
{
    int i, j, x, y, k;
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            d1[i][j] = oo;
    d1[xj][yj] = 1;
    queue< pair <int, int> >q;
    q.push(make_pair(xj, yj));
    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(Inside(x, y) && a[x][y] == 0 && d1[x][y] > d1[i][j] + 1)
            {
                d1[x][y] = d1[i][j] + 1;
                q.push(make_pair(x, y));
            }
        }
    }
}

int main()
{
    int i, j;
    fin >> n >> m;
    fin.get();
    for (int i = 1;i <= n;++i)
    {
        fin.getline(s + 1, 255);
        for (int j = 1;j <= m;++j)
        {
            if (s[j] == ' ')
                a[i][j] = 0;
            else if (s[j] == 'X')
                a[i][j] = 1;
            else if (s[j] == 'R')
            {
                xr = i;
                yr = j;
            }
            else if (s[j] == 'J')
            {
                xj = i;
                yj = j;
            }
        }
    }
    Lee();
    Lee2();
    for(i = 1;i <= n;i++, cout << "\n")
        for(j = 1;j <= m;j++, cout << " ")
            cout << a[i][j];
    int sol = oo, soli, solj;
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            if(d[i][j] != oo && d1[i][j] != oo && d[i][j] == d1[i][j])
                if(d[i][j] < sol)
                {
                    sol = d[i][j];
                    soli = i;
                    solj = j;
                }
    fout << sol << " " << soli << " " << solj;
    return 0;
}