Cod sursa(job #1889498)

Utilizator gorneanu.andreiFMI Gorneanu Andrei gorneanu.andrei Data 22 februarie 2017 19:05:01
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <vector>
#include <queue>
using namespace std;
int n, m, a[105][105], xR, yR, xJ, yJ;
char mat[150][150];
vector <int> vJ, vR, q[10001];

void citire(){

    fstream f("rj.in",ios::in);
    f >> n >> m;
    int i, j;
    f.getline(mat[0],150,'\n');

    for(i = 0;i < n; ++i)
        f.getline(mat[i],150,'\n');


    for(i = 0;i <= n + 1; ++i)
        a[i][m + 1] = a[i][0] = 0;
    for(i = 0;i <= m + 1; ++i)
        a[n + 1][i] = a[0][i] = 0;

    for(i = 0;i < n; ++i){
        for(j = 0;j < m; ++j){
            if(mat[i][j] == 'J'){
                xJ = i + 1;
                yJ = j + 1;
                a[i + 1][j + 1] = -1;
                continue;
            }
            if(mat[i][j] == 'R'){
                xR = i + 1;
                yR = j + 1;
                a[i + 1][j + 1] = -1;
                continue;
            }
            if(mat[i][j] == ' '){
                a[i + 1][j + 1] = 1;
                continue;
            }
            if(mat[i][j] == 'X'){
                a[i + 1][j + 1] = 0;
                continue;
            }
        }
    }
    f.close();
}

void liniarizare(){

    int i, j;
    for(i = 1;i <= n; ++i)
        for(j = 1;j <= m; ++j){
            if(a[i][j]){
                if(a[i + 1][j]){
                    q[(i-1) * n + j].push_back(i * n + j);
                    q[i * n + j].push_back((i-1) * n + j);
                }
                if(a[i][j + 1]){
                    q[(i-1) * n + j].push_back((i-1) * n + j + 1);
                    q[(i-1) * n + j + 1].push_back((i-1) * n + j);
                }
                if(a[i + 1][j + 1]){
                    q[i * n + j + 1].push_back((i-1) * n + j);
                    q[(i-1) * n + j].push_back(i * n + j + 1);
                }
                if(a[i - 1][j]){
                    q[(i-1) * n + j].push_back((i - 2) * n + j);
                    q[(i - 2) * n + j].push_back((i-1) * n + j);
                }
                if(a[i][j - 1]){
                    q[(i-1) * n + j].push_back((i-1) * n + j - 1);
                    q[(i-1) * n + j - 1].push_back((i-1) * n + j);
                }
                if(a[i - 1][j - 1]){
                    q[(i-1) * n + j].push_back((i - 2) * n + j - 1);
                    q[(i - 2) * n + j - 1].push_back((i-1) * n + j);
                }
                if(a[i - 1][j + 1]){
                    q[(i-1) * n + j].push_back((i - 2) * n + j + 1);
                    q[(i - 2) * n + j + 1].push_back((i-1) * n + j);
                }
                if(a[i + 1][j - 1]){
                    q[(i-1) * n + j].push_back(i * n + j - 1);
                    q[i * n + j - 1].push_back((i-1) * n + j);
                }
            }
    }

}

void print(vector <int> vJ){

    fstream g("rj.out",ios::out);
    int mid = vJ.size() / 2 + 1, x, y;
    g << mid << " ";
    x = vJ[mid] / n;
    if(vJ[mid] % m)
        ++n;
    y = vJ[mid] % m;
    g << x << " " << y;

    g.close();
}


void BFS(int nod,vector <int> v[10001],vector <int> p,int final){

    queue <int> qu;
    int vizitat[n * m], i, S, tata[n * m];
    for(i = 1;i <= n * m; ++i)
        vizitat[i] = tata[i] = -1;

    qu.push(nod);
    tata[nod] = 0;

    while(!qu.empty()){
        S = qu.front();
        qu.pop();
        vizitat[S] = 1;
        if(S == final)
            break;
        int len = v[S].size();
        for(i = 0;i < len; ++i)
            if(vizitat[v[S][i]] == -1){
                qu.push(v[S][i]);
                vizitat[v[S][i]] = 1;
                tata[v[S][i]] = S;
            }
    }

    int x;
    x = final;

    while(x){
        p.push_back(x);
        x = tata[x];
    }

    print(p);
}



int main(){

    citire();
    liniarizare();
    BFS((xJ-1) * n + yJ,q,vJ,(xR-1) * n + yR);
    //BFS((xR-1) * n + yR,q,vR,(xJ-1) * n + yJ);




}