Cod sursa(job #1333870)

Utilizator BrandonChris Luntraru Brandon Data 3 februarie 2015 17:45:39
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <cstdio>
#include <queue>
using namespace std;
struct POINT
{
    int x, y;
};
POINT rom, jul;
queue <POINT> q;
int n, m, mat[101][101], dr[101][101], dj[101][101];
int dir[8][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} };
char ch;
void read()
{
    freopen("rj.in", "r", stdin);
    scanf("%d%d\n", &n, &m);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            scanf("%c", &ch);
            if ( ch == '\n' ) {
                -- j;
                continue;
            }
            if(ch == 'X')
                mat[i][j] = 1;
            if(ch == 'R')
            {
                rom.x = i;
                rom.y = j;
            }
            if(ch == 'J')
            {
                jul.x = i;
                jul.y = j;
            }
        }
    }
}
void bordare()
{
    for(int i = 0; i <= n+1; ++i)
    {
        mat[i][0] = 1;
        mat[i][m+1] = 1;
    }
    for(int j = 0; j <= m+1; ++j)
    {
        mat[0][j] = 1;
        mat[n+1][j] = 1;
    }
}
void print()
{
    freopen("rj.out", "w", stdout);
    POINT poz_sol;
    int min = 101;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            if(dr[i][j] == dj[i][j] && dr[i][j] < min && !mat[i][j])
            {
                min = dr[i][j];
                poz_sol.x = i;
                poz_sol.y = j;
            }
        }
    printf("%d %d %d\n", min, poz_sol.x, poz_sol.y);
}
void solve(int d[][101], POINT s)
{
    q.push(s);
    d[s.x][s.y] = 1;
    while(!q.empty())
    {
        POINT first = q.front();
        q.pop();
        for(int i = 0; i < 8; ++i)
        {
            POINT next;
            next.x = first.x + dir[i][0];
            next.y = first.y + dir[i][1];
            if(!mat[next.x][next.y] && !d[next.x][next.y])
            {
                d[next.x][next.y] = d[first.x][first.y]+1;
                q.push(next);
            }
        }
    }
}
int main()
{
    read();
    bordare();
    solve(dr, rom);
    solve(dj, jul);
    print();
    return 0;
}