Cod sursa(job #3004677)

Utilizator albertaizicAizic Albert albertaizic Data 16 martie 2023 15:33:26
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <stdio.h>
#include <deque>
using namespace std;
#define NMax 102
#define DIR 8

struct pct{
  int x,y;
};
int n,m,xr,yr,xj,yj,tmin,xf,yf;
int dl[DIR]={-1,-1,-1, 0, 0, 1, 1, 1};
int dc[DIR]={-1, 0, 1,-1, 1,-1, 0, 1};
char l[NMax][NMax];
int d[NMax][NMax];
int ver[NMax][NMax];
deque <pct> q;

void lee2(){
  int i,o=0;
  q.push_front({xr,yr});
  ver[xr][yr]=1;
  d[xr][yr]=1;
  q.push_front({xj,yj});
  ver[xj][yj]=2;
  d[xj][yj]=1;
  while(!q.empty() && o==0){
    pct p=q.back();
    q.pop_back();
    for(i=0;i<DIR;i++)
      if(l[p.x+dl[i]][p.y+dc[i]]==' '){
        if(ver[p.x+dl[i]][p.y+dc[i]]==0){
          d[p.x+dl[i]][p.y+dc[i]]=1+d[p.x][p.y];
          ver[p.x+dl[i]][p.y+dc[i]]=ver[p.x][p.y];
          q.push_front({p.x+dl[i],p.y+dc[i]});
        }else if(ver[p.x+dl[i]][p.y+dc[i]]!=ver[p.x][p.y] && o==0 && d[p.x+dl[i]][p.y+dc[i]]==d[p.x][p.y]+1){
          o=1;
          xf=p.x+dl[i];
          yf=p.y+dc[i];
          tmin=d[p.x+dl[i]][p.y+dc[i]];
        }
      }
	}
}

int main(){
  FILE *fin,*fout;
  int i,j;
  char c;
  fin=fopen("rj.in","r");
  fout=fopen("rj.out","w");
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<=n+1;i++)
    l[i][0]=l[i][m+1]='X';
  for(i=0;i<=m+1;i++)
    l[0][i]=l[n+1][i]='X';

  for(i=1;i<=n;i++){
    c=fgetc(fin);
    for(j=1;j<=m;j++){
      c=fgetc(fin);
      l[i][j]=c;
      if(l[i][j]=='R'){
        xr=i;
        yr=j;
        l[i][j]=' ';
      }
      if(l[i][j]=='J'){
        xj=i;
        yj=j;
        l[i][j]=' ';
      }
    }
  }
  lee2();
  fprintf(fout,"%d %d %d",tmin,xf,yf);
  fclose(fin);
  fclose(fout);
  return 0;
}