Cod sursa(job #1579886)

Utilizator andreiskiorAndrei Cristian Nastase andreiskior Data 25 ianuarie 2016 10:29:02
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <stdio.h>
#include <ctype.h>
#include <queue>

using std::queue;
using std::pair;
using std::make_pair;

int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,1,-1,1,-1};

queue < pair <int, int> > Q;

int n,m;
int hartar[100][100];
int hartaj[100][100];

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    char s[100];
    int i,j,ic,jc,ji,jj,dir;
    scanf("%d %d\n",&n,&m);
    for(i = 0; i < n ; ++i)
    {
        gets(s);
        for(j = 0; j < m; ++j)
        {
            if(isspace(s[j]))
                hartar[i][j] = hartaj[i][j] = 0;
            else
                if(s[j] == 'X')
                    hartar[i][j] = hartaj[i][j] = -1;
                 else
                    if(s[j] == 'R')
                        Q.push(make_pair(i,j));
                    else
                    {
                        ji = i;
                        jj = j;
                    }

        }
    }
    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for(dir = 0; dir < 4; ++dir)
        {
            ic = i + dx[dir];
            jc = j + dy[dir];
            if(ic >= 0 && jc >= 0 && ic < n && jc < m && hartar[ic][jc] == 0)
            {
                hartar[ic][jc] = hartar[i][j] + 1;
                Q.push(make_pair(ic,jc));
            }
        }
    }
    Q.push(make_pair(ji,jj));
    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for(dir = 0; dir < 7; ++dir)
        {
            ic = i + dx[dir];
            jc = j + dy[dir];
            if(ic >= 0 && jc >= 0 && ic < n && jc < m && hartaj[ic][jc] == 0)
            {
                hartaj[ic][jc] = hartaj[i][j] + 1;
                Q.push(make_pair(ic,jc));
            }
        }
    }
    int mini,minj,minim = 101 * 101;
    for(i = 0; i < n; ++i){
        for(j = 0; j < m ; ++j)
            if(hartar[i][j] == hartaj[i][j] && hartar[i][j] < minim && hartar[i][j] > 0)
                {
                    mini = i;
                    minj = j;
                    minim = hartar[i][j];
                }
    }
    printf("%d %d %d\n",minim,mini+1,minj+1);
    return 0;
}