Cod sursa(job #2668346)

Utilizator Edwuard99Diaconescu Vlad Edwuard99 Data 4 noiembrie 2020 19:57:44
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <cstdio>
#include <string>
#define maxn 101
#include <queue>
using namespace std;

char x[maxn][maxn];
bool viz[maxn][maxn];
int n, m;
struct nod { int i, j;nod(){}; nod(int a, int b){i=a; j=b;};};
const int xx[9]={-1,-1,0,1,1,1 ,0 ,-1};
const int yy[9]={ 0, 1,1,1,0,-1,-1,-1};
short dr[maxn][maxn], dj[maxn][maxn];
nod r, J;
void read()
{
    freopen("rj.in","r",stdin);
    scanf("%d %d\n", &n, &m);
    int i;
    for(i=0;i<n;++i) gets(x[i]);
}

void bfsr(nod s)
{
    queue<nod>Q;
    Q.push(s);
    int i, newi, newj;
    nod u;
    memset(viz, 0,sizeof(viz));
    viz[s.i][s.j]=1;
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        //	printf("%d %d\n", u.i, u.j);
        for(i=0;i<8;++i)
        {
            newi=u.i+xx[i];
            newj=u.j+yy[i];
            //	printf("%d %d\n", newi, newj);
            if(newi>=0 && newi<n && newj>=0 && newj<m)
                if(x[newi][newj]!='X' && !viz[newi][newj])
                {
                    dr[newi][newj]=dr[u.i][u.j]+1;
                    viz[newi][newj]=1;
                    Q.push(nod(newi,newj));
                }
        }
    }

}

void bfsj(nod s)
{
    queue<nod>Q;
    Q.push(s);
    int i, newi, newj;
    nod u;
    memset(viz, 0,sizeof(viz));

    viz[s.i][s.j]=1;
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        for(i=0;i<8;++i)
        {
            newi=u.i+xx[i];
            newj=u.j+yy[i];
            if(newi>=0 && newi<n && newj>=0 && newj<m)
                if(x[newi][newj]!='X' && !viz[newi][newj])
                {
                    dj[newi][newj]=dj[u.i][u.j]+1;
                    viz[newi][newj]=1;
                    Q.push(nod(newi,newj));
                }
        }
    }

}

int main()
{
    read();
    int i, j;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            if(x[i][j]=='R') r.i=i, r.j=j;
            else if(x[i][j]=='J') J.i=i, J.j=j;

    bfsr(r);
    bfsj(J);
    //	printf("\n");
    //for(i=0;i<n;++i)
    {
//		for(j=0;j<m;++j)printf("%d ", dj[i][j]);
        //	printf("\n");
    }

    int min=0x3f3f3f3f, pi=-1, pj=-1;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            if(x[i][j]==' ')
                if(dr[i][j]==dj[i][j] && dr[i][j])
                    if(min>dr[i][j]) min=dr[i][j], pi=i, pj=j;

    freopen("rj.out","w",stdout);
    printf("%d %d %d\n", min+1, pi+1, pj+1);

    return 0;
}