Cod sursa(job #2450899)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 24 august 2019 20:40:51
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <bits/stdc++.h>

using namespace std;
FILE *IN;

int di[8] = {0, 0, -1, 1, 1, -1, 1, -1};
int dj[8] = {-1, 1, 0, 0, 1, 1, -1, -1};

int N, M;
int mat[105][105];
int par[2][105][105];
pair <int, int> pos[2];

queue <pair <int, int> > Q;

int read(){
    int ok, cnt = 0;
    char ch;
    scanf("%d %d ", &N, &M);
    for(int i = 1; i <= N; i++){
        ok = 1;
        for(int j = 1; j <= M; j++){
            scanf("%c", &ch);
            if(ch == ' ')
                mat[i][j] = 1;
            else if(ch == 'X')
                mat[i][j] = 0;
            else if(ch == 'J' || ch == 'R'){
                mat[i][j] = 2;
                pos[cnt].first = i;
                pos[cnt++].second = j;
            } else {
                ok = 0;
                break;
            }
        }
        if(ok) scanf("%c", &ch);
    }
}

bool OK(int i, int j){
    if(i < 1 || j < 1 || i > N || j > N)
        return false;
    if(!mat[i][j])
        return false;
    return true;
}

int lee(int mat[2][105][105], int x, int y, int l){
    Q.push(make_pair(x, y));
    mat[l][x][y] = 1;
    while(Q.size()){
        int i = Q.front().first;
        int j = Q.front().second;
        //printf("%d ", i);
        for(int d = 0; d < 8; d++){
            int ii = i + di[d];
            int jj = j + dj[d];
            if(OK(ii, jj) && mat[l][ii][jj] == 2e9){
                mat[l][ii][jj] = mat[l][i][j] + 1;
                Q.push(make_pair(ii, jj));
            }
        }
        Q.pop();
    }
}

int init(int l){
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            par[l][i][j] = 2e9;
}

int main(){

    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    read();
    init(0); lee(par, pos[0].first, pos[0].second, 0);
    init(1); lee(par, pos[1].first, pos[1].second, 1);

    int ans = 2e9, posians, posjans;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(par[0][i][j] == par[1][i][j] && par[1][i][j] < ans){
                ans = par[0][i][j];
                posians = i;
                posjans = j;
            }
        }
    }
    printf("%d %d %d", ans, posians, posjans);

    return 0;
}