Cod sursa(job #342163)

Utilizator PopaStefanPopa Stefan PopaStefan Data 20 august 2009 18:35:43
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
//Acest program rezolva problema romeo si julieta (Enunt in acelasi folder)
//ALGORITMUL LEE CU MATRICE (50 puncte pe infoarena)
//Depaseste timpul de executie (ineficient)
#include<fstream.h>

ifstream fin("rj.in");
ofstream fout("rj.out");

int n,m,x1,y1,x2,y2;
int a[101][101];
int rom[101][101];
int jul[101][101];
int l[8]={-1,-1,-1,0,1,1,1,0};
int c[8]={-1,0,1,1,1,0,-1,-1};

void citire()
{int i,j;
char c;
fin>>n>>m;
fin.get(c);
for(i=1;i<=n;i++)
  {for(j=1;j<=m;j++)
       {fin.get(c);
       if(c==' ') a[i][j]=0;
         else if(c=='X') a[i][j]=1;
                else if(c=='R') {x1=i;
                                 y1=j;
                                }
                       else {x2=i;
                             y2=j;
                            }

        }
   fin.get(c);
   if(c!='\n')
     while(c!='\n')
        fin.get(c);
  }
}

void lee()
{int i,j,ii,jj,k,pas=1;
typedef enum{DA,NU} boolean;
boolean gata=NU;
rom[x1][y1]=1;
jul[x2][y2]=1;
while(gata==NU)
  {gata=DA;
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     if(rom[i][j]==jul[i][j] && rom[i][j]==pas) {fout<<pas<<" "<<i<<" "<<j;
                                                 exit(0);
                                                }
      else if(rom[i][j]==pas) for(k=0;k<=7;k++)
                                {ii=i+l[k];
                                 jj=j+c[k];
                                 if(ii>=1 && ii<=n && jj>=1 && jj<=m)
                                    if(a[ii][jj]==0 && rom[ii][jj]==0)
                                      {rom[ii][jj]=pas+1;
                                       gata=NU;
                                      }
                                }

         else if(jul[i][j]==pas) for(k=0;k<=7;k++)
                                   {ii=i+l[k];
                                    jj=j+c[k];
                                    if(ii>=1 && ii<=n && jj>=1 && jj<=m)
                                        if(a[ii][jj]==0 && jul[ii][jj]==0)
                                            {jul[ii][jj]=pas+1;
                                             gata=NU;
                                            }
                                   }




   pas++;
  }
}

int main()
{citire();
lee();
fin.close();
fout.close();
return 0;
}