Cod sursa(job #2124799)

Utilizator sichetpaulSichet Paul sichetpaul Data 7 februarie 2018 16:47:08
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
int a[101][101];char s[101];
short int b[101][101];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
queue <int> lin;
queue <int> col;
int main()
{ int n,m,i,j,x,y,sol,l,c,rr,jj,x1,y1,p;
    ifstream f("rj.in");
    ofstream g("rj.out");
    f>>n>>m;
    for (i=1;i<=n;++i) {
        f.get();
        f.get(s,101);
    for (j=1;j<=m;++j) {
        if (s[j-1]==' ') a[i][j]=0;
        if (s[j-1]=='X') a[i][j]=-1;
        if (s[j-1]=='R') a[i][j]=1;
        if (s[j-1]=='J') a[i][j]=2;
    }
    }

    sol=n*m+1;
       for (i=0;i<=n+1;++i)
        a[i][0]=a[i][m+1]=-1;
    for (j=0;j<=m+1;++j)
        a[0][j]=a[n+1][j]=-1;
    for (i=1;i<=n;++i)
    for (j=1;j<=m;++j)
    if (a[i][j]==0) {
        lin.push(i);
        col.push(j);
        b[i][j]=1;
        rr=jj=0;
        while (!lin.empty()) {
            l=lin.front();
            c=col.front();
            for (p=0;p<4;++p) {
                x=l+dx[p];
                y=c+dy[p];
                if (a[x][y]!=-1 && !b[x][y]) {
                    b[x][y]=b[l][c]+1;
                    if (a[x][y]==0) lin.push(x),col.push(y);
                    else {
                        if (a[x][y]==1) rr=b[x][y];
                        else jj=b[x][y];
                    }
                }
            }
            lin.pop();col.pop();
            if (rr && jj) break;
        }
        if (rr==jj && rr>0)
        if (rr<sol) {
            sol=rr;
            x1=i,y1=j;
        }
        for (x=1;x<=n;++x)
        for (y=1;y<=m;++y)
          b[x][y]=0;
    }
      g<<sol-1<<" "<<x1<<" "<<y1;
    return 0;
}