Cod sursa(job #1128959)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 27 februarie 2014 19:24:35
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.43 kb
#include    <iostream>
#include    <fstream>
#include    <cstring>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

struct orice
{
    short int l, c;
}ro[3000], gi[3000];

short int map[102][102], N, M;
short int mapR[102][102], mapG[102][102];
void read()
{
    fin >> N;
    fin >> M;
    char line[100];
    for(int i = 1; i <= N + 1; i++)
    {
        fin.getline(line,100);
        int len = strlen(line);
        for(int j = 0; j < len; j++)
        {
            if(int(line[j]) == 32) map[i-1][j+1] = 32000;
            if(int(line[j]) == 88) map[i-1][j+1] = -1;
            if(int(line[j]) == 82) 
            {
                map[i-1][j+1] = 0;
                ro[0].l = i - 1;
                ro[0].c = j + 1;
            }
            if(int(line[j]) == 74)
            {
                map[i-1][j+1] = 0;
                gi[0].l = i - 1;
                gi[0].c = j + 1;
            }
        }
    }
    /*
    *   Set the margins
    */
    for(int i = 0; i <= M+1; i++)
	{
        map[0][i] =    -1;
        map[N+1][i] =  -1;
	}
	for(int i = 0; i <= N+1; i++)
	{
        map[i][0] =    -1;
        map[i][M+1] =  -1;
	}
    return;
}

int di[8] = {0,1,0,-1,1,-1,-1,1};
int dj[8] = {1,0,-1,0,1,-1,1,-1};

void lee_ro()
{
    int ex = 0, nr = 0;
    while(ex <= nr)
    {
        int l, c;
        l = ro[ex].l;
        c = ro[ex].c;
        for(int i = 0; i < 8; i ++)
        {
            if(map[l][c] + 1 < map[l + di[i]][c + dj[i]])
            {
                map[l + di[i]][c + dj[i]] = map[l][c] + 1;
                mapR[l + di[i]][c + dj[i]] = map[l][c] + 1;
                nr += 1;
                ro[nr].l = l + di[i];
                ro[nr].c = c + dj[i];
            }
        }
        ex += 1;
    }
}

void lee_gi()
{
    int ex = 0, nr = 0;
    while(ex <= nr)
    {
        int l, c;
        l = gi[ex].l;
        c = gi[ex].c;
        for(int i = 0; i < 8; i ++)
        {
            if(map[l][c] + 1 <= map[l + di[i]][c + dj[i]])
            {
                map[l + di[i]][c + dj[i]] = map[l][c] + 1;
                mapG[l + di[i]][c + dj[i]] = map[l][c] + 1;
                nr += 1;
                gi[nr].l = l + di[i];
                gi[nr].c = c + dj[i];
            }
        }
        ex += 1;
    }
}

void show()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

void showR()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            cout << mapR[i][j] << " ";
        }
        cout << "\n";
    }
}

void showG()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            cout << mapG[i][j] << " ";
        }
        cout << "\n";
    }
}
short int maxvalue = 30000, valuei, valuej;
void solve()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            if((mapR[i][j] == mapG[i][j]) && mapR[i][j] > 0)
            {
                int value;
                value = mapR[i][j];
                if(value < maxvalue)
                {
                    valuei = i;
                    valuej = j;
                    maxvalue = value;
                }
            }
        }
    }
}
int main()
{
    read();
    lee_ro();
    lee_gi();
    solve();
    //showR();
    //cout << "\n";
    //showG();
    fout << maxvalue + 1 << " " << valuei << " " << valuej;
    //show();
    return 0;
}