Cod sursa(job #2810988)

Utilizator MariusDinsorea32DinsoreanMarius MariusDinsorea32 Data 30 noiembrie 2021 20:16:49
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <bits/stdc++.h>

using namespace std;

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

queue <pair <int, int>> q;

const int N = 104;

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

bool used[N][N], blocked[N][N];
int d[N][N];
int dist[N][N];

int n, m, i, j, e, f, x, y, z, l, c, ln, cn, l1, c1, mi = 10000004;
char s[N];

bool inside(int a, int b)
{
    if(a >= 1 && a <= n && b >= 1 && b <= m) return true;
    return false;
}


int main()
{
    fin >> n >> m;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            d[i][j] = dist[i][j] = 10009;
    fin.get();
    for(i = 1; i <= n; i++)
    {
        fin.getline(s, 107);
        for(j = 0; j < m; j++)
        {
            if(s[j] == 'X') blocked[i][j + 1] = true;
            else if(s[j] == 'R') x = i, y = j + 1;
            else if(s[j] == 'J') e = i, f = j + 1;
        }
    }
    d[x][y] = 1;
    used[x][y] = true;
    q.push(make_pair(x, y));
    while(q.empty() == 0)
    {
        pair<int, int> coord = q.front();
        l = coord.first;
        c = coord.second;
        for(i = 0; i < 8; i++)
        {
            ln = l + lin[i];
            cn = c + col[i];
            if(inside(ln, cn) && !used[ln][cn] && !blocked[ln][cn])
            {
                d[ln][cn] = d[l][c] + 1;
                used[ln][cn] = true;
                q.push(make_pair(ln, cn));
            }
        }
        q.pop();
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++) used[i][j] = false;
    dist[e][f] = 1;
    used[e][f] = true;
    q.push(make_pair(e, f));
    while(q.empty() == 0)
    {
        pair<int, int> coord = q.front();
        l = coord.first;
        c = coord.second;
        for(i = 0; i < 8; i++)
        {
            ln = l + lin[i];
            cn = c + col[i];
            if(inside(ln, cn) && !used[ln][cn] && !blocked[ln][cn])
            {
                dist[ln][cn] = dist[l][c] + 1;
                used[ln][cn] = true;
                q.push(make_pair(ln, cn));
            }
        }
        q.pop();
    }
    /*
    for(i = 1; i <= n; i++, fout << "\n")
        for(j = 1; j <= m; j++) fout << d[i][j] << " ";
    fout << "\n";
    for(i = 1; i <= n; i++, fout << "\n")
        for(j = 1; j <= m; j++) fout << dist[i][j] << " ";
    */
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            if(d[i][j] == dist[i][j])
            {
                if(mi > d[i][j])
                {
                    mi = d[i][j];
                    l1 = i;
                    c1 = j;
                }
                else if(mi == d[i][j] && l1 > i) l1 = i, c1 = j;
                else if(mi == d[i][j] && l1 == i && c1 > j) c1 = j;
            }
        }
    }
    fout << mi << " " << l1 << " " << c1;
    return 0;
}