Cod sursa(job #1468224)

Utilizator elevenstrArina Raileanu elevenstr Data 5 august 2015 15:35:42
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <iostream>
#include <queue>
#include <cstdio>
#include <fstream>
#include <cstring>
using namespace std;
#define ex -1
ifstream in("rj.in");
ofstream out("rj.out");
const int MAX=150;
char t[150];
int ro [MAX][MAX],ju [MAX][MAX];
inline int inside(int x,int y,int n,int m)
{
    return x>=1 and x<=n and y>=1 and y<=m;
}
queue<pair<int,int> > Qr;
queue<pair<int,int> > Qj;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int main()
{
int x_n,y_n,x,y,n,m,i,j,tim=100000;

    in>>n;
    in>>m;
    in.get();
  for(i=1;i<=n;i++)
  {
      in.getline(t+1,m+1);
    for(j=1;j<=m;j++)
      {
          if((char)t[j]=='X') {ro[i][j]=-1; ju[i][j]=-1;  }
      if((char)t[j]=='R') {ro[i][j]=1; Qr.push(make_pair(i,j));}
      if((char)t[j]=='J') {ju[i][j]=1; Qj.push(make_pair(i,j));}}

  }

  while(!Qr.empty())
  {
      x=Qr.front().first;
      y=Qr.front().second;
      Qr.pop();
      for(i=0;i<=7;i++)
      {
          x_n=x+dx[i];
          y_n=y+dy[i];
          if(inside(x_n,y_n,n,m)==0)continue;
          if(ro[x_n][y_n]==0|| ro[x_n][y_n]>ro[x][y]+1){
            ro[x_n][y_n]=ro[x][y]+1;
            Qr.push(make_pair(x_n,y_n));
          }
      }
  }

  while(!Qj.empty())
  {
      x=Qj.front().first;
      y=Qj.front().second;
      Qj.pop();
      for(i=0;i<=7;i++)
      {
          x_n=x+dx[i];
          y_n=y+dy[i];
          if(inside(x_n,y_n,n,m)==0)continue;
          if(ju[x_n][y_n]==0|| ju[x_n][y_n]>ju[x][y]+1){
            ju[x_n][y_n]=ju[x][y]+1;
            Qj.push(make_pair(x_n,y_n));
          }
      }
  }

    x=0; y=0;
for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
   if(ro[i][j]==ju[i][j]&&ro[i][j]!=-1&&ro[i][j]<tim&&ro[i][j]!=0){tim=ro[i]
[j]; x=i; y=j;}
out<<tim<<" "<<x<<" "<<y;

    return 0;
}