Cod sursa(job #1065841)

Utilizator andreiiiiPopa Andrei andreiiii Data 23 decembrie 2013 19:00:30
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N=105;

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

int d[2][N][N], dx[]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[]={0, 1, 1, 1, 0, -1, -1, -1};
PII start[2];
char a[N][N];
int n, m;

bool ok(int x, int y)
{
    if(x<1||x>n) return 0;
    if(y<1||y>m) return 0;
    if(a[x][y]=='X') return 0;
    return 1;
}

void lee(int u)
{
    int i;
    queue <PII> q;
    PII p;
    memset(d[u], INF, sizeof(d[u]));
    d[u][start[u].x][start[u].y]=1;
    q.push(start[u]);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(i=0;i<8;i++)
        {
            if(ok(p.x+dx[i], p.y+dy[i])&&d[u][p.x+dx[i]][p.y+dy[i]]>d[u][p.x][p.y]+1)
            {
                d[u][p.x+dx[i]][p.y+dy[i]]=d[u][p.x][p.y]+1;
                q.push(make_pair(p.x+dx[i], p.y+dy[i]));
            }
        }
    }
}

int main()
{
    int i, j, sol=INF, l, c;
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
    {
        fin.getline(a[i]+1, N);
        for(j=1;j<=m;j++)
        {
            if(a[i][j]=='R') start[0]=make_pair(i, j);
            else if(a[i][j]=='J') start[1]=make_pair(i, j);
        }
    }
    lee(0);
    lee(1);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(d[0][i][j]==d[1][i][j]&&d[1][i][j]&&d[1][i][j]&&d[1][i][j]<sol)
            {
                sol=d[0][i][j];
                l=i;
                c=j;
            }
        }
    }
    fout<<sol<<" "<<l<<" "<<c;
    fin.close();
    fout.close();
}