Cod sursa(job #889553)

Utilizator lucianRRuscanu Lucian lucianR Data 24 februarie 2013 16:24:29
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.51 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");

string line;
short int matJ[101][101], matR[101][101], x1, y1, x2, y2, qx[10000], qy[10000], top, minr=10000, xx, yy, x, y, n, m, ok;
const short int dx[]={0,1,1,1,0,-1,-1,-1};
const short int dy[]={1,1,0,-1,-1,-1,0,1};

void read()
{
    in>>n>>m;
    getline(in,line);
    for(short int i=0; i<n; i++)
    {
        getline(in,line);
        for(short int j=0; j<m; j++)
        {
            if(line[j]=='R')
            {
                matR[i][j]=1;
                x1=i;
                y1=j;
            }
            if(line[j]=='J')
            {
                matJ[i][j]=1;
                x2=i;
                y2=j;
            }
            if(line[j]=='X')
            {
                matR[i][j]=-1;
                matJ[i][j]=-1;
            }
        }
    }

}

bool goodR(short int row,short int col)
{
    return (row>=0) && (col>=0) && (row<n) && (col<m) && (matR[row][col]==0);
}

bool goodJ(short int row,short int col)
{
    return (row>=0) && (col>=0) && (row<n) && (col<m) && (matJ[row][col]==0);
}

void Romeo()
{
    for(short int i=0; i<top; i++)
    {
        x=qx[i];
        y=qy[i];
        for(short int k=0; k<8; k++)
        {
            if(goodR(x+dx[k],y+dy[k]))
            {
                matR[x+dx[k]][y+dy[k]]=matR[x][y]+1;
                qx[top]=x+dx[k];
                qy[top]=y+dy[k];
                top++;
            }
        }
    }
}

void Juliet()
{
    for(short int i=0; i<top; i++)
    {
        x=qx[i];
        y=qy[i];
        for(short int k=0; k<8; k++)
        {
            if(goodJ(x+dx[k],y+dy[k]))
            {
                matJ[x+dx[k]][y+dy[k]]=matJ[x][y]+1;
                qx[top]=x+dx[k];
                qy[top]=y+dy[k];
                top++;
            }
        }
    }
}

int main()
{
    read();

    qx[0]=x1;
    qy[0]=y1;
    top=1;
    Romeo();

    for(short int i=0; i<top; i++)
    {
        qx[i]=0;
        qy[i]=0;
    }
    qx[0]=x2;
    qy[0]=y2;
    top=1;
    Juliet();

    for(short int i=0; i<n; i++)
    {
        for(short int j=0; j<m; j++)
        {
            if(matR[i][j]==matJ[i][j] && matJ[i][j]<minr && matR[i][j]!=-1 && matR[i][j]!=0)
            {
                xx=i; yy=j; minr=matR[i][j]; cout<<"DAA"<<xx<<" "<<yy<<endl;
            }
        }
    }
    /*for (short int i=0; i<n; i++)
    {
        for (short int j=0; j<m; j++)
            out<<matR[i][j]<<" ";
        out<<endl;
    }
    for (short int i=0; i<n; i++)
    {
        for (short int j=0; j<m; j++)
            out<<matJ[i][j]<<" ";
        out<<endl;
    }*/
    out<<minr<<" "<<xx+1<<" "<<yy+1;
    in.close();
    out.close();
    return 0;
}



























/*string line;
short int n, m, x1, y1, x2, y2, mat[100][100], xc, yc, qx[10000], qy[10000], s, f, xx=-1, yy=-1;
bool visited[100][100];
const short int dx[]={0, -1, -1, -1, 0, 1, 1, 1};
const short int dy[]={-1, -1, 0, 1, 1, 1, 0, -1};

void read() {
    in>>n>>m; getline(in,line);
    for(short int i=0; i<n; i++) {
        getline(in,line);
        for(short int j=0; j<m; j++) {
            if(line[j]=='R') {
                x1=i; y1=j;
                mat[i][j]=1;
            }
            if(line[j]=='J') {
                x2=i; y2=j;
                mat[i][j]=-1;
            }
            if(line[j]==' ') {
                mat[i][j]=0;
            }
            if(line[j]=='X') {
                mat[i][j]=99;
            }
        }
    }
}

bool good(short int row, short int col) {
    return (row>=0) && (row<n) && (col>=0) && (col<m) && (mat[row][col]!=99);
}

short int roadR() {
    while(s<f) {
        xc=qx[s];
        yc=qy[s];
        visited[xc][yc]=1;
        for(short int i=0; i<8; i++) {
            if(good(xc+dx[i],yc+dy[i]) && mat[xc+dx[i]][yc+dy[i]]==mat[xc][yc]+1) {
                    xx=xc+dx[i];
                    yy=yc+dy[i];
                    out<<xx<<yy<<"XX\n";

                }
            if(good(xc+dx[i],yc+dy[i]) && (mat[xc][yc]<mat[xc+dx[i]][yc+dy[i]] || mat[xc+dx[i]][yc+dy[i]]==0)) {
                qx[f]=xc+dx[i]; cout<<qx[f]<<" ";
                qy[f]=yc+dy[i]; cout<<qy[f];
                mat[xc+dx[i]][yc+dy[i]]=mat[xc][yc]+1; //cout<<mat[xc+dx[i]][yc+dy[i]]<<" ";
                f++;
                for(short int i=0; i<n; i++) {
                    for(short int j=0; j<m; j++)
                        out<<mat[i][j]<<" ";
                    out<<"\n";
                }
                out<<xc<<" "<<yc<<" \n\n";
            }


        }

        cout<<endl;
        s++;
    }
}

short int roadJ() {
    while(s<f && xx==-1) {
        cout<<"DAAA";
        xc=qx[s];
        yc=qy[s];
        visited[xc][yc]=1;
        for(short int i=0; i<8; i++) {
            if(good(xc+dx[i],yc+dy[i])) {
                if(mat[xc+dx[i]][yc+dy[i]]*(-1)==mat[xc][yc]-1) {
                    xx=xc+dx[i];
                    yy=yc+dy[i];
                    out<<xx<<yy<<"XX\n";

                }
                else
                    if(mat[xc+dx[i]][yc+dy[i]]>0) {
                        qx[f]=xc+dx[i]; cout<<qx[f]<<" ";
                        qy[f]=yc+dy[i]; cout<<qy[f];
                        mat[xc+dx[i]][yc+dy[i]]=mat[xc][yc]-1; //cout<<mat[xc+dx[i]][yc+dy[i]]<<" ";
                        f++;
                        for(short int i=0; i<n; i++) {
                            for(short int j=0; j<m; j++)
                                out<<mat[i][j]<<" ";
                            out<<"\n";
                        }
                out<<xc<<" "<<yc<<" \n\n";
                    }
            }
        }

        cout<<endl;
        s++;
    }
}

int main()
{
    read();
    qx[0]=x1;
    qy[0]=y1;
    f=1;
    for(short int i=0; i<n; i++) {
        for(short int j=0; j<m; j++)
            out<<mat[i][j]<<" ";
        out<<"\n";
    }
    roadR();
    for(short int i=0; i<n; i++) {
        for(short int j=0; j<m; j++)
            visited[i][j]=0;
    }
    for(int i=0; i<f; i++) {
        qx[i]=0;
        qy[i]=0;
    }
    qx[0]=x2;
    qy[0]=y2;
    f=1; s=0;
    roadJ();
    for(short int i=0; i<n; i++) {
        for(short int j=0; j<m; j++)
            out<<mat[i][j]<<" ";
        out<<"\n";
    }
    out<<mat[xx][yy]<<" "<<xx+1<<" "<<yy+1;
    in.close();
    out.close();
    return 0;
}
*/