Cod sursa(job #1631406)

Utilizator ajeccAjechiloae Eugen ajecc Data 5 martie 2016 15:42:48
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <fstream>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#define for0(i,n) for(int i=0; i<n; i++)
#define for1(i,n) for(int i=1; i<=n; i++)
#define pb push_back
#define mp make_pair
#define ALL(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define clr(A,x) memset(A, x, sizeof(A))
#define cpy(A,B) memcpy(A, B, sizeof(B))
#define g(s) getline(fin, s) ///mod
#define FASTIO ios_base::sync_with_stdio(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAX=100005;
const ull MOD=100003;
const int NR_CIFRE=100005;
/*template <typename T>
string to_string(const T& n){
    ostringstream os;
    os << n;
    return os.str();
}
*/
ifstream fin("rj.in");
ofstream fout("rj.out");

int n, m;
int mat[101][101];
int rx, ry, jx, jy;
int matcpy[101][101];

void citire();
int lee(int startx, int starty, int finalx, int finaly);

struct coord
{
    int x, y;
};
queue<coord> coada;
int dx[]={0, 0, -1, 1, 1, 1, -1, -1};
int dy[]={1, -1, 0, 0, 1, -1, 1, -1};


int main()
{
    citire();
    int sol=100000000;
    int solx, soly;
    for1(i, n)
        for1(j, m)
        {
            if(mat[i][j]==0)
            {
                int aux=lee(rx, ry, i, j);
                int aux2=lee(jx, jy, i, j);
                if(aux==aux2)
                {
                    if(sol>aux)
                    {
                        sol=aux;
                        solx=i;
                        soly=j;
                    }
                }
            }
        }

    fout<<sol<<' '<<solx<<' '<<soly;



    return 0;
}

void citire()
{
    fin>>n>>m;
    string s;
    g(s); ///mod
    for1(i, n)
    {
        g(s);
        for0(j, m)
        {
            char x=s[j];
            //cin>>x;
            if(x=='R')
            {
                mat[i][j+1]=1;
                rx=i;
                ry=j+1;
            }
            else if(x=='J')
            {
                mat[i][j+1]=1;
                jx=i;
                jy=j+1;
            }
            else if(x=='X')
                mat[i][j+1]=-1;
        }
    }

    cpy(matcpy, mat);
}

int lee(int startx, int starty, int finalx, int finaly)
{
    coord p;
    p.x=startx;
    p.y=starty;
    coada.push(p);

    while(!coada.empty() && mat[finalx][finaly]==0)
    {
        p=coada.front();
        coada.pop();
        for0(k, 8)
        {
            coord pnou;
            pnou.x=p.x+dx[k];
            pnou.y=p.y+dy[k];

            if(pnou.x<=n && pnou.x>=1 &&
               pnou.y<=m && pnou.y>=1 &&
               mat[pnou.x][pnou.y]==0)
            {
                coada.push(pnou);
                mat[pnou.x][pnou.y]=mat[p.x][p.y]+1;
            }
        }
    }
    while(!coada.empty())
        coada.pop();
    int ret=mat[finalx][finaly];
    cpy(mat, matcpy);
    return ret==0?102010:ret;
}