Cod sursa(job #1801186)

Utilizator saba_alexSabadus Alex saba_alex Data 8 noiembrie 2016 19:10:56
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
/// 100p pe infoarena, problema era la aa.y<=n in loc de m
#include <iostream>
#include <string.h>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream g("rj.out");

struct coord {int x, y;};
coord s, f, rr, jj;
int R[105][105], J[105][105], n, m, i, j;
const int dx[8]={-1,0,1,1,1,0,-1,-1}, dy[8]={1,1,1,0,-1,-1,-1,0};
queue<coord> c;
char ch[105];

void Lee(int d[][105], coord s)
{   d[s.x][s.y]=1;
    c.push(s);
    while (!c.empty())
    {   coord a=c.front();
        c.pop();
        for(int k=0;k<8;k++)
        {   coord aa;
            aa.x=a.x+dx[k];
            aa.y=a.y+dy[k];
            if(aa.x>0 && aa.y>0 && aa.x<=n && aa.y<=m && d[aa.x][aa.y]==0)
            {   d[aa.x][aa.y]=d[a.x][a.y]+1;
                c.push(aa);
            }
        }
    }
}

int main()
{   fin>>n>>m;
    for(i=0;i<=n;i++)
    {   fin.getline(ch,105);
        for(j=0;j<strlen(ch);j++)
        {   if (ch[j]=='R')//retinem locatia lui Romeo
            {   rr.x=i;
                rr.y=j+1;
            }
            if (ch[j]=='J')//retinem locatia lui Julieta
            {   jj.x=i;
                jj.y=j+1;
            }
            if (ch[j]=='X')//marcam obstacolele in ambele matrici
            {   R[i][j+1]=-1;
                J[i][j+1]=-1;
            }
        }
    }
    //algoritmul lui Lee pt matricea lui R si J
    Lee(R, rr);
    Lee(J, jj);

    for(i=1;i<=n;i++)
    {   for(j=1;j<=m;j++)
           cout<<R[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;
    for(i=1;i<=n;i++)
    {   for(j=1;j<=m;j++)
           cout<<J[i][j]<<' ';
        cout<<endl;
    }
    int minn=1<<30,ii=0,jj=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if (R[i][j]==J[i][j] && R[i][j]>0 ) //daca e punct comun si nu e obstacol
            {   if (R[i][j]<minn)
                {   minn=R[i][j];
                    ii=i; jj=j;
                }
            }

    g<<minn<<' '<<ii<<' '<<jj<<' ';
    return 0;
}