Cod sursa(job #2489573)

Utilizator nustiuVlada Misici nustiu Data 8 noiembrie 2019 23:22:35
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>

using namespace std;
FILE *IN;

int di[] = {0, 0, -1, 1, 1, -1, 1, -1};
int dj[] = {-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;

void citire(){
    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);
    }
}

/*void afis(int l){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(par[l][i][j] != 2e9){
                printf("%d", par[l][i][j]);
                if(par[l][i][j] > 9) printf(" ");
                else printf("  ");
            } else printf("0  ");
        }
        printf("\n");
    }
}*/

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

void 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;
        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] > mat[l][i][j] + 1){
                mat[l][ii][jj] = mat[l][i][j] + 1;
                Q.push(make_pair(ii, jj));
            }
        }
        Q.pop();
    }
}

void 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);

    citire();
    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;
}