Cod sursa(job #1436933)

Utilizator lucaignatescuIgnatescu Luca lucaignatescu Data 16 mai 2015 17:16:50
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
//
//  main.cpp
//  Rj
//
//  Created by Cristian Ignatescu on 16/05/15.
//  Copyright (c) 2015 Luca Ignatescu. All rights reserved.
//

#include <cstdio>
#include <queue>
#include <fstream>
using namespace std;
struct punct
{
    int x,y;
};
queue <punct> Q;

const int INF = 2000000000;

int M[105][105];
int Mr[105][105];
int Mj[105][105];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n,m;

void Lee(int mat[][105], punct start)
{
    for (int i = 1; i <=n; ++ i)
        for (int j = 1; j <= n; ++ j)
        {
            mat[i][j] = INF;
        }
    mat[start.x][start.y] = 0;
    Q.push(start);
    while(!Q.empty())
    {
        punct a=Q.front();
        Q.pop();
        for (int i = 0; i < 8; ++i)
        {
            punct now;
            now.x = a.x + dx[i];
            now.y = a.y + dy[i];
            if (M[now.x][now.y] != -1 && mat[a.x][a.y] + 1 < mat[now.x][now.y])
                mat[now.x][now.y]=mat[a.x][a.y]+1,Q.push(now);
        }
        
    }
}

int main() {
    //freopen("rj.in", "r", stdin);
    freopen("rj.out","w",stdout);
    ifstream f("rj.in");
    char c;
    int i,j,tmin=1;
    f >> n >> m;
    punct R,J,a;
    for(i = 1; i <= n; ++i){
        char s[105];
        f.getline(s, 105);
        for(j = 1; j <= m; ++j)
        {
            char c = s[j];
            if(c==' ')
                M[i][j]=0;
            if(c=='X')
                M[i][j]=-1;
            if(c=='R')
                R.x=i,R.y=j,Mr[i][j]=1;
            if(c=='J')
                J.x=i,J.y=j,Mj[i][j]=1;
        }
    }
    for(j=0;j<=m+1;++j)
        M[0][j]=-1;
    for(i=1;i<=n+1;++i)
        M[i][0]=-1;
    for(j=1;j<=m+1;++j)
        M[n+1][j]=-1;
    for(i=1;i<=n;++i)
        M[i][m+1]=-1;
    Lee(Mr,R);
    Lee(Mj,J);
    int maxim=INF;
    punct ans;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            if(M[i][j]!=-1 && Mr[i][j]==Mj[i][j] && Mr[i][j]<maxim)
            {
                maxim=Mr[i][j];
                ans.x=i;
                ans.y=j;
            }
        }
    printf("%d %d %d\n",maxim,ans.x,ans.y);
    return 0;
}