Cod sursa(job #1688831)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 13 aprilie 2016 19:14:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
typedef short matrice[102][102];
matrice a;
bitset <102>ef[102];
bitset <102>es[102];
char d[101];
int dx[]={0,0,1,0,-1,-1,1,-1,1};
int dy[]={0,1,0,-1,0,-1,1,1,-1};
int n,m,i,j,xr,yr,xj,yj;
queue < pair <char, char> >coada;
int kr(int x, int y)
{
    return x>=1 && x<=n && y>=1 && y<=m && a[x][y]==0;
}
int kj(int x, int y)
{
    return x>=1 && x<=n && y>=1 && y<=m && a[x][y]!=-1 && !ef[x][y];
}
void leer(char x, char y)
{
    char i,j,i2,j2,k;
    a[x][y]=1;
    coada.push(make_pair(x,y));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(k=1;k<=8;k++)
        {
            i2=i+dx[k];
            j2=j+dy[k];
            if(kr(i2,j2))
            {
                a[i2][j2]=1+a[i][j];
                coada.push(make_pair(i2,j2));
            }
        }
    }
}
void leej(char x, char y)
{
    char i,j,i2,j2,k;
    a[x][y]=1;
    ef[x][y]=1;
    coada.push(make_pair(x,y));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(k=1;k<=8;k++)
        {
            i2=i+dx[k];
            j2=j+dy[k];
            if(kj(i2,j2))
            {
                if(a[i2][j2]==a[i][j]+1)es[i2][j2]=1;
                ef[i2][j2]=1;
                a[i2][j2]=a[i][j]+1;
                coada.push(make_pair(i2,j2));
            }
        }
    }
}
void afis(matrice a)
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)cout<<a[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"\n";
}
int main()
{
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
    {
        memset(d,0,sizeof(d));
        fin.getline(d,m+2);
        for(j=1;j<=m;j++)
        {
            if(d[j-1]=='X')a[i][j]=-1;
            if(d[j-1]=='J')xj=i,yj=j;
            if(d[j-1]=='R')xr=i,yr=j;
        }
    }
    leer(xr,yr);
    afis(a);
    leej(xj,yj);
    afis(a);
    int mi=2000000000,xs,ys;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(es[i][j])
            if(mi>a[i][j])mi=a[i][j],xs=i,ys=j;
    fout<<mi<<" "<<xs<<" "<<ys<<"\n";
    return 0;
}