Cod sursa(job #3141983)

Utilizator turistuMarian Marinciuc turistu Data 18 iulie 2023 09:47:59
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, a[101][101], b[101][101], ans = INT_MAX, ansx, ansy;
int x1, x2, x3, x4;
int dx[] = {-1, -1, 1, 1, -1, 1, 0, 0};
int dy[] = {-1, 1, -1, 1, 0, 0, -1, 1};

bool inmat(int i, int j){
    return i>=1 && j>=1 && i<=n && j<=m;
}

void lee(int is, int js, int t){
    if(t == 1){
        queue<pair<int, int>> q;
        q.push(make_pair(is, js));
        a[is][js] = 1;
        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for(int d = 0; d<=7; d++){
                int inou = dx[d] + x;
                int jnou = dy[d] + y;
                if(inmat(inou, jnou) && a[inou][jnou] == 0){
                    a[inou][jnou] = a[x][y] + 1;
                    q.push(make_pair(inou, jnou));
                }
            }
        }
    }
    else{
        queue<pair<int, int>> q;
        q.push(make_pair(is, js));
        b[is][js] = 1;
        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for(int d = 0; d<=7; d++){
                int inou = dx[d] + x;
                int jnou = dy[d] + y;
                if(inmat(inou, jnou) && b[inou][jnou] == 0){
                    b[inou][jnou] = b[x][y] + 1;
                    q.push(make_pair(inou, jnou));
                }
            }
        }
    }
}

int main(){
    fin >> n >> m;

    for(int i = 1; i<=n; i++)
        for(int j = 0; j<=m; j++){
            char s;
            fin.get(s);
            if(s == ' ');
            else if(s == 'R')
                x1 = i, x2 = j;
            else if(s == 'J')
                x3 = i, x4 = j;
            else if(s == 'X')
                a[i][j] = b[i][j] = -1;
        }

    lee(x1, x2, 1);
    lee(x3, x4, 2);

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

    fout << ans << ' ' << ansx << ' ' << ansy;

    return 0;
}