Cod sursa(job #1383996)

Utilizator CartofJohnsonFMI Tanasescu Andrei CartofJohnson Data 10 martie 2015 19:55:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <fstream>
using namespace std;
int v[105][105],w[105][105],n,m,pa,pb,da,db;
char *q;
int main()
{
        FILE *fin=fopen("rj.in","r");
		FILE *fout=fopen("rj.out","w");
        fscanf(fin,"%d %d",&n,&m);
		q=(char*)malloc(106);
        int temp1=n+1,a=0;
        while(a<=temp1){v[a][0]=v[a][m+1]=-1;a++;}
        a=0;temp1=m+1;
        while(a<=temp1){v[0][a]=v[n+1][a]=-1;a++;}
        int b;
        for(int a=1;a<=n;a++){
             fscanf(fin," %[^\n]",q);
            for(b=0;b<m;b++){
                int temp1=q[b];
                if(temp1=='X'){v[a][b+1]=-1;continue;}
                if(temp1=='R'){v[a][b+1]=0,da=a,db=b+1;continue;}
                if(temp1=='J'){pa=a,pb=1+b,v[a][b+1]=99999999;continue;}
                v[a][b+1]=99999999;
            }
        }
        temp1=n+1;int temp2=m+1;
        for(int a=0;a<=temp1;a++)
        for(int b=0;b<=temp2;b++)
            w[a][b]=v[a][b];
        w[pa][pb]=0;
        w[da][db]=99999999;
 
 
        int dx[]={-1,-1,-1,0,0,1,1,1};
        int dy[]={-1,0,1,-1,1,-1,0,1};
        int ok;
        do
        {
            ok=0;
            for(int a=1;a<=n;a++)
            for(int b=1;b<=m;b++)
            {
                if(v[a][b]>=0)
                {
                    for(int c=0;c<8;c++)
                    if(v[a+dx[c]][b+dy[c]]>=0)
                    if(v[a][b]+1<v[a+dx[c]][b+dy[c]])
                    v[a+dx[c]][b+dy[c]]=v[a][b]+1,ok=1;
                }
                if(w[a][b]>=0)
                {
                    for(int c=0;c<8;c++)
                    if(w[a+dx[c]][b+dy[c]]>=0)
                    if(w[a][b]+1<w[a+dx[c]][b+dy[c]])
                    w[a+dx[c]][b+dy[c]]=w[a][b]+1,ok=1;
                }
            }
        }while(ok==1);
        int qa,qb,c=99999999;
        for(int a=1;a<=n;a++)
        for(int b=1;b<=m;b++)
        if(v[a][b]>=0 && v[a][b]==w[a][b])
        if(v[a][b]<c)
            c=v[a][b],qa=a,qb=b;
        fprintf(fout,"%d %d %d",c+1,qa,qb);
 
}