Cod sursa(job #1365721)

Utilizator grimmerFlorescu Luca grimmer Data 28 februarie 2015 14:40:08
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
char a[102][102];
int d1[102][102],d2[102][102];
const int dlin[]= {-1,-1,-1,1,1,1,0,0};
const int dcol[]= {-1,1,0,-1,1,0,-1,1};
struct poz
{
    int lin, col;
};
poz q[10001];
int n,m;
void bordare()
{
    register int i;
    for(i=0; i<=n+1; i++)
    {
        a[i][0] = 'X';
        a[i][m+1] = 'X';
    }
    for(i=0; i<=m+1; i++)
    {
        a[0][i] = 'x';
        a[n+1][i] = 'x';
    }
}
int main()
{
    int i,j,u=-1,p=0,min;
    ifstream in("rj.in");
    ofstream out("rj.out");
    in>>n>>m>>ws;
    poz r,ju,x,y,rez;
    for(i=1; i<=n; i++)
        in.getline(1+a[i],101);
    bordare();
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(a[i][j]=='R')
            {
                r.lin = i;
                r.col = j;
            }
            else if (a[i][j]=='J')
            {
                ju.lin = i;
                ju.col = j;
            }
        }
    }
    q[++u] = r;
    d1[r.lin][r.col] = 1;
    while(p<=u)
    {
        x = q[p++];
        for(i=0; i<8; i++)
        {
            y.lin = x.lin + dlin[i];
            y.col = x.col + dcol[i];
            if((a[y.lin][y.col] == ' ' || a[y.lin][y.col] == 'J') && d1[y.lin][y.col] == 0)
            {
                q[++u] = y;
                d1[y.lin][y.col] = 1 + d1[x.lin][x.col];
            }
        }
    }
    u = -1;
    p = 0;
    q[++u] = ju;
    d2[ju.lin][ju.col] = 1;
    while(p<=u)
    {
        x = q[p++];
        for(i=0; i<8; i++)
        {
            y.lin = x.lin + dlin[i];
            y.col = x.col + dcol[i];
            if((a[y.lin][y.col] == ' ' || a[y.lin][y.col] == 'R') && d2[y.lin][y.col] == 0){
                q[++u] = y;
                d2[y.lin][y.col] = 1 + d2[x.lin][x.col];
            }
        }
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(d1[i][j] != 0 && d2[i][j] != 0)
                if(d1[i][j] == d2[i][j] && d1[i][j] <= min){
                    min = d1[i][j];
                    rez.lin = i;
                    rez.col = j;
                }
    out<<min<<" "<<rez.lin<<" "<<rez.col;
    return 0;
}