Cod sursa(job #78547)

Utilizator andrei_infoMirestean Andrei andrei_info Data 18 august 2007 14:58:11
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb

#include <pair.h>
#include <queue.h>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

#define MAX 105
#define INF 999999

char mat[MAX][MAX];
int rom[MAX][MAX], jul[MAX][MAX], n,m, rx,ry, jx,jy;

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

void citire()
{
    ifstream fin;
    fin.open ("rj.in", ifstream::in);
    fin>>n>>m;

    for (int i = 0; i<=n+1; i++)
    {
        mat[0][i] = 'X';
        mat[m+1][i] = 'X';
    }
    for (int i = 0; i<=m+1; i++)
    {
        mat[i][0] = 'X';
        mat[i][n+1] = 'X';
    }
    char s[105];
    fin.getline(s,105);
    for (int i = 1; i<=n; i++)
    {

          fin.getline(s,105);

          for (int j = 1; j<=m; j++)
          {
            mat[i][j] = s[j-1];
            if (mat[i][j] == 'R')
            {
                    mat[i][j] = ' ';
                    rx = i; ry = j;
            }
            if (mat[i][j] == 'J')
            {
                    mat[i][j] = ' ';
                    jx = i; jy = j;
            };
          }
    }
    fclose(stdin);
};

void fill( int x, int y, int unde[MAX][MAX])
{
    typedef pair < int, int > P;

    queue < P > Q;

    for (int i = 0; i<=n; i++)
        for (int j=0; j<=m; unde[i][j++] = INF);
    Q.push( P (x,y) );
    unde[x][y] = 0;

    while (!Q.empty() )
    {
        P aux = Q.front();
        Q.pop();

        int xx = aux.first, yy = aux.second;

        for (int k = 0; k<8; k++)
            if ( mat[xx+dx[k]][yy+dy[k]] == ' ' && unde[xx+dx[k]][yy+dy[k]] == INF)
            {
                unde[xx+dx[k]][yy+dy[k]] = unde[xx][yy]+1;
                Q.push( P ( xx+dx[k], yy+dy[k]) );
            }
    };
}

void afis()
{
    int tmin=INF, xx=1,yy=1;
    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=m; j++)
            if (rom[i][j] == jul[i][j] && rom[i][j] < tmin )
            {
                tmin = rom[i][j];
                xx = i; yy = j;
            };
    ofstream fout ("rj.out");

    fout<< tmin+1<<' '<<xx<<' '<< yy;
    fout.close();

}
void afis_mat( int ce[MAX][MAX])
{
    for (int i =  1; i<=n; i++)
    {
        for (int j = 1;j<=m; j++)
            printf("%8d", ce[i][j]);
    printf("\n");
    };
};



int main()
{
    citire();
    fill(rx, ry, rom);
    //afis_mat(rom);
    fill(jx, jy, jul);
    //afis_mat(jul);
    afis();
    return 0;
};