Cod sursa(job #1377683)

Utilizator teoutzzzNeacsu Teodor teoutzzz Data 5 martie 2015 23:43:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.3 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<string.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue<int> qx;
queue<int> qy;
 int x,x1,y,y1,xx,yy,i,j,m,n,mat1[100][100],mat2[100][100],c1,c2,minim=32000;
void lee1()
{

    qx.push(x);
    qy.push (y);
    while(xx!=x1 || yy!=y1)
    {
        xx=qx.front();
        yy=qy.front();
        if(mat1[xx-1][yy]==0|| mat1[xx-1][yy]>mat1[xx][yy]+1){
            mat1[xx-1][yy]=mat1[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy);
    }
        if(mat1[xx+1][yy]==0||mat1[xx+1][yy]>mat1[xx][yy]+1){
            mat1[xx+1][yy]=mat1[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy);
    }
        if(mat1[xx][yy-1]==0||mat1[xx][yy-1]>mat1[xx][yy]+1){
            mat1[xx][yy-1]=mat1[xx][yy]+1;
            qx.push(xx);
            qy.push(yy-1);
    }
         if(mat1[xx][yy+1]==0||mat1[xx][yy+1]>mat1[xx][yy]+1){
            mat1[xx][yy+1]=mat1[xx][yy]+1;
            qx.push(xx);
            qy.push(yy+1);
         }

        if(mat1[xx+1][yy+1]==0||mat1[xx+1][yy+1]>mat1[xx][yy]+1){
            mat1[xx+1][yy+1]=mat1[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy+1);
            }
        if(mat1[xx-1][yy+1]==0||mat1[xx-1][yy+1]>mat1[xx][yy]+1){
            mat1[xx-1][yy+1]=mat1[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy+1);
        }
        if(mat1[xx+1][yy-1]==0||mat1[xx+1][yy-1]>mat1[xx][yy]+1){
            mat1[xx+1][yy-1]=mat1[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy-1);
        }
        if(mat1[xx-1][yy-1]==0||mat1[xx-1][yy-1]>mat1[xx][yy]+1){
            mat1[xx-1][yy-1]=mat1[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy-1);
        }
    qx.pop();
    qy.pop();
    }
    mat1[x][y]=0;

}
void lee2()
{

    qx.push(x1);
    qy.push (y1);
    while(xx!=x || yy!=y)
    {
        xx=qx.front();
        yy=qy.front();
        if(mat2[xx-1][yy]==0|| mat2[xx-1][yy]>mat2[xx][yy]+1){
            mat2[xx-1][yy]=mat2[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy);
    }
        if(mat2[xx+1][yy]==0||mat2[xx+1][yy]>mat2[xx][yy]+1){
            mat2[xx+1][yy]=mat2[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy);
    }
        if(mat2[xx][yy-1]==0||mat2[xx][yy-1]>mat2[xx][yy]+1){
            mat2[xx][yy-1]=mat2[xx][yy]+1;
            qx.push(xx);
            qy.push(yy-1);
    }
         if(mat2[xx][yy+1]==0||mat2[xx][yy+1]>mat2[xx][yy]+1){
            mat2[xx][yy+1]=mat2[xx][yy]+1;
            qx.push(xx);
            qy.push(yy+1);
         }

        if(mat2[xx+1][yy+1]==0||mat2[xx+1][yy+1]>mat2[xx][yy]+1){
            mat2[xx+1][yy+1]=mat2[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy+1);
            }
        if(mat2[xx-1][yy+1]==0||mat2[xx-1][yy+1]>mat2[xx][yy]+1){
            mat2[xx-1][yy+1]=mat2[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy+1);
        }
        if(mat2[xx+1][yy-1]==0||mat2[xx+1][yy-1]>mat2[xx][yy]+1){
            mat2[xx+1][yy-1]=mat2[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy-1);
        }
        if(mat2[xx-1][yy-1]==0||mat2[xx-1][yy-1]>mat2[xx][yy]+1){
            mat2[xx-1][yy-1]=mat2[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy-1);
        }
    qx.pop();
    qy.pop();
    }
 mat2[x1][y1]=0;
}
int main()
{

	char v[100];
	f>>n>>m;
    f.get();
    for(i=1; i<=n; i++)
    {
       f.getline(v,m+1);
       for(j=0;j<=m; j++)
            {
        if( v[j]== 'X'){ mat1[i][j+1]=-1; mat2[i][j+1]=-1;}
            else if( v[j] == 'R') {x=i;y=j+1;}
                   else if(v[j] == 'J') {x1=i;y1=j+1;}
            }
    }
         for(i=0;i<=m+1;i++){mat1[0][i]=-1;
                       mat1[n+1][i]=-1;
                       mat2[0][i]=-1;
                       mat2[n+1][i]=-1;}
    for(i=0;i<=n+1;i++){mat1[i][0]=-1;
                       mat1[i][m+1]=-1;
                       mat2[i][0]=-1;
                       mat2[i][m+1]=-1;}
          lee2();
          lee1();
     for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(mat1[i][j]>0 &&mat1[i][j]==mat2[i][j]&&mat1[i][j]<minim){minim=mat1[i][j];c1=i;c2=j;}
         g<<minim+1<<" "<<c1<<" "<<c2;
        f.close();
        g.close();
        return 0;
}