Cod sursa(job #212533)

Utilizator EdeNNu Cred EdeN Data 5 octombrie 2008 19:58:41
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.93 kb
#include <iostream>
#include <stdio.h>
#include <queue>

using namespace std;
int n,m,i,j,x1,x2,y1,y2;
char a[100][100];
int b[100][100] ,c[100][100];
struct coo {int x,y;};
struct val {int x,y,v;};
queue <coo> coada;

void scan()
{
    string s;
    char buffer[100];
    freopen("rj.in","r",stdin);
    scanf("%d %d",&n,&m);
    gets(buffer);
    for (i=0; i<n; i++)
        {
            gets(buffer);
            s=buffer;
            for (j=0; j<s.length(); j++)
                {
                    if (s[j]=='R')
                        {
                            x1=i;
                            y1=j;
                        }
                    if (s[j]=='J')
                        {
                            x2=i;
                            y2=j;
                        }
                a[i][j]=s[j];
                }
        }
}

void look(int b[100][100], int x1, int y1)
{
    int auxx, auxy;
    coo nod;
    nod.x=x1;
    nod.y=y1;
    coada.push(nod);
    b[x1][y1]=1;
    while (coada.size()>0)
        {
            auxx=coada.front().x;
            auxy=coada.front().y;
            coada.pop();

            if (auxx-1>=0 && a[auxx-1][auxy]!='X' && b[auxx-1][auxy]==0)
            {
                b[auxx-1][auxy]=b[auxx][auxy]+1;
                nod.x=auxx-1;
                nod.y=auxy;
                coada.push(nod);
            }

            if (auxy+1<m && a[auxx][auxy+1]!='X' && b[auxx][auxy+1]==0)
            {
                b[auxx][auxy+1]=b[auxx][auxy]+1;
                nod.x=auxx;
                nod.y=auxy+1;
                coada.push(nod);
            }

            if (auxx+1<n && a[auxx+1][auxy]!='X' && b[auxx+1][auxy]==0)
            {
                b[auxx+1][auxy]=b[auxx][auxy]+1;
                nod.x=auxx+1;
                nod.y=auxy;
                coada.push(nod);
            }

            if (auxy-1>=0 && a[auxx][auxy-1]!='X' && b[auxx][auxy-1]==0)
            {
                b[auxx][auxy-1]=b[auxx][auxy]+1;
                nod.x=auxx;
                nod.y=auxy-1;
                coada.push(nod);
            }

            if (auxy+1<m && auxx-1>=0 && a[auxx-1][auxy+1]!='X' && b[auxx-1][auxy+1]==0)
            {
                b[auxx-1][auxy+1]=b[auxx][auxy]+1;
                nod.x=auxx-1;
                nod.y=auxy+1;
                coada.push(nod);
            }

            if (auxy+1<m && auxx+1<n && a[auxx+1][auxy+1]!='X' && b[auxx+1][auxy+1]==0)
            {
                b[auxx+1][auxy+1]=b[auxx][auxy]+1;
                nod.x=auxx+1;
                nod.y=auxy+1;
                coada.push(nod);
            }

            if (auxy-1>=0 && auxx+1<n && a[auxx+1][auxy-1]!='X' && b[auxx+1][auxy-1]==0)
            {
                b[auxx+1][auxy-1]=b[auxx][auxy]+1;
                nod.x=auxx+1;
                nod.y=auxy-1;
                coada.push(nod);
            }

            if (auxy-1>=0 && auxx-1>=0 && a[auxx-1][auxy-1]!='X' && b[auxx-1][auxy-1]==0)
            {
                b[auxx-1][auxy-1]=b[auxx][auxy]+1;
                nod.x=auxx-1;
                nod.y=auxy-1;
                coada.push(nod);
            }
        }
}

void search()
{
    coo nod;
    for (i=0; i<n; i++)
        for (j=0; j<m; j++)
            if (b[i][j]==c[i][j] && b[i][j]!=0 && c[i][j]!=0)
                {
                    nod.x=i;
                    nod.y=j;
                    coada.push(nod);
                }
}

void writeit(int x[100][100])
{
    for (int i=0; i<n; i++)
        {
            for (int j=0; j<m; j++)
                cout << x[i][j];
            cout << endl;
        }
}

int main()
{
    val min;
    scan();
    look(b,x1,y1);
    look(c,x2,y2);
    writeit(b);
    cout <<endl;
    writeit(c);
    search();
    min.x=coada.front().x;
    min.y=coada.front().y;
    min.v=b[min.x][min.y];
    coada.pop();
    while (coada.size()>0)
        {
            if (min.v>b[coada.front().x][coada.front().y])
                {
                    min.v=b[coada.front().x][coada.front().y];
                    min.x=coada.front().x;
                    min.y=coada.front().y;
                }
            else
                    if (min.v==b[coada.front().x][coada.front().y] && min.x>coada.front().x)
                        {
                            min.x=coada.front().x;
                            min.y=coada.front().y;
                        }
                    else
                            if (min.v==b[coada.front().x][coada.front().y] && min.x==coada.front().x && min.y>coada.front().y)
                                {
                                    min.y=coada.front().y;
                                }
            coada.pop();
        }
    cout << min.x << " " << min.y << " " << min.v;
    freopen("rj.out","w",stdout);
    cout << min.v << " " << min.x+1 << " " << min.y+1;
    return 0;
}