Cod sursa(job #1851288)

Utilizator antanaAntonia Boca antana Data 19 ianuarie 2017 16:45:11
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <queue>
#include <cstring>

#define MAXN 101

using namespace std;

queue < pair<int, int> > q;

int n, m, seen[MAXN][MAXN], d[2][MAXN][MAXN];
char s[MAXN+1];

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

void bfs(int startx, int starty, int nr)
{
    int row, col, i, nextX, nextY;

    q.push({startx, starty});

    seen[startx][starty] = 1;
    d[nr][startx][starty] = 1;

    while(!q.empty())
    {
        row = q.front().first;
        col = q.front().second;

        q.pop();

        for(i=0; i<8; ++i)
        {
            nextX = row + dx[i];
            nextY = col + dy[i];
            if(nextX > 0 && nextX <= n && nextY > 0 && nextY <= m && seen[nextX][nextY] == 0)
            {
                d[nr][nextX][nextY] = d[nr][row][col] + 1;
                seen[nextX][nextY] = 1;
                q.push({nextX, nextY});
            }
        }
    }
}

int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    int i, j, rx, ry, jx, jy, minans = 0x3f3f3f3f, row, col, aux;

    scanf("%d%d\n", &n, &m);

    for(i=1; i<=n; ++i)
    {
        gets(s+1);

        j = 1;
        aux = strlen(s+1);

        while(j < aux)
        {
            if(s[j] == 'X') seen[i][j] = -1;
            if(s[j] == 'R') rx = i, ry = j;
            if(s[j] == 'J') jx = i, jy = j;
            j++;
        }
    }

    bfs(rx, ry, 0);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            if(seen[i][j] == 1)
                seen[i][j] = 0;

    bfs(jx, jy, 1);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            if(d[0][i][j] == d[1][i][j] && seen[i][j] == 1)
                if(minans > d[0][i][j])
                    minans = d[0][i][j], row = i, col = j;

    printf("%d %d %d", minans, row, col);

    return 0;
}