114 Muzeu

[•Anduu]

Imi ziceti va rog ce inseamna KBS 6 (SIGABRT)? Din cauza la asta nu iau 3 teste.  ](*,)Daca e nevoie de sursa, ziceti-mi si vi-o dau prin PM.

[•repp4radu]

Fi atent la limite. Declari matricea de 251 si accesezi elementul 251 in functia bordare(indexarea unui vector incepe de la 0, deci ultimul element este N - 1). Ai putea sa iei KBS de la asta.

[•Anduu]

Mersi, a mers!

[•Sapientia]

Am facut cu algoritmul lui Le...i-am introdus in coada pe gardieni...dar nu stiu de ce i-au pe testele 3,4,9 killed by signal http://www.infoarena.ro/job_detail/1023715...sursa: http://www.infoarena.ro/job_detail/1023715?action=view-source.

[•romircea2010]

Salut, incearca while-ul asta

Cod:

while(!d.empty())
    {
        int x,y;
        x=d.front();d.pop_front();
        y=d.front();d.pop_front();
        lee(x,y);
        x=d.front();d.pop_front();
        y=d.front();d.pop_front();
        lee(x,y);
    }

sa-l inlocuiesti cu asta

Cod:

while(!d.empty())
    {
        int x,y;
        x=d.front();d.pop_front();
        y=d.front();d.pop_front();
        lee(x,y);
    }

[•Sapientia]

Merge..nu stiu de ce am mi-a venit sa apelez de doua ori functia lee(x,y).. si mai ales nu stiu de ce in prima faza am luat wa pe alea 3 teste.

[•romircea2010]

nu ai luat wa, ai luat kbs. in prima faza exista posibilitatea ca deque-ul pe care il foloseai sa devina vid inainte sa apelezi x=d.front(); d.pop_front(); ... a doua oara

[•Sapientia]

Da....multumesc de ajutor!

[•otniel]

de ce iau pe aceasta sursa killed by signal 11 si incorect
#include<iostream>
using namespace std;
int a[260][260],i,j,n,inceput=1,sfarsit=1;
int const x1[4]={1,-1,0,0};
int const y1[4]={0,0,1,-1};
char c;
struct pct
{
    int ls,ld,d;
};
pct coada[260],x,y;
#include<stdio.h>
FILE *f,*g;
int main()
{
    f=fopen("muzeu.in","r");
    g=fopen("muzeu.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fscanf(f,"%c",&c);
            if(c=='.')
                a[j]=0;
            else
                if(c=='#')
                a[j]=-2;
            else
                if(c=='P')
                a[j]=-1;
                else
                    if(c=='\n')
                    j--;
        }
       for(i=0;i<=n;i++)
       {
           a

• =-2;

           a[n+1]=-2;
           a[0]=-2;
           a[n+1]=-2;
       }
       a[n+1][n+1]=-2;
       for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(a[j]==-1)
       {coada[inceput].ls=i;
       coada[inceput].ld=j;
       coada[inceput].d=0;
           while(inceput<=sfarsit)
           {
               x=coada[inceput];
               coada[inceput].ls=coada[inceput].ld=coada[inceput].d=0;
               inceput++;
              for(int k=0;k<4;k++)
                if(a[x.ls+x1[k]][x.ld+y1[k]]==0)
                {
                    a[x.ls+x1[k]][x.ld+y1[k]]=x.d+1;
                    y.d=x.d+1;
                    y.ls=x.ls+x1[k];
                    y.ld=x.ld+y1[k];
                    sfarsit++;
                    coada[sfarsit]=y;
                }
                else
                    if(a[x.ls+x1[k]][x.ld+y1[k]]!=0&&a[x.ls+x1[k]][x.ld+y1[k]]!=-1&&a[x.ls+x1[k]][x.ld+y1[k]]!=-2)
                {
                    if(x.d+1<a[x.ls+x1[k]][x.ld+y1[k]])
                    {
                        a[x.ls+x1[k]][x.ld+y1[k]]=x.d+1;
                    y.d=x.d+1;
                    y.ls=x.ls+x1[k];
                    y.ld=x.ld+y1[k];
                    sfarsit++;
                    coada[sfarsit]=y;
                    }
                }

           }

            for(int u=1;u<=sfarsit;u++)
            {
                coada.ls=coada.ld=coada.d=0;
            }
            sfarsit=inceput=1;
       }
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
if(a[j]==0)
fprintf(g,"-1 ");
else
    if(a[j]==-1)
    fprintf(g,"0 ");
else
    fprintf(g,"%d ",a[j]);
fprintf(g,"\n");
}
}

[•otniel]

as putea primi si niste teste ca deja ma dispera problema aceasta?

[•otniel]

rezolvat.era de la spatiul alocat pentru memorie si faptul ca nu retineam toti paznici odata

[•BaltaretuAndrei]

E foarte simplu ><
In coada adaugi fiecare paznic la inceput dupa care iei fiecare elemnnt din coada si il extinzi.
Va chinuiti foarte mult cu back tracking + ca da tle si cand primesti killed by signal 11 inseamna ca ai declarat ori prea multa memorie ori prea putina nu e grea am 80 de randuri in total 

[•breahnadavid]

Eu n-am folosit, algoritmul lui Lee,, pentru că am considerat  că găsesc ceva mai eficient..
Dar m-am împotmolit..  nu reuÈ™esc să iau decît 80 de puncte.. îmi spune È™i mie cineva de ce iau doar atît..
Adică unde pierd în timp,, pentru că eu consider că timpii embilor algoritmi ar trebui să fie egali.. ??

http://www.infoarena.ro/job_detail/1199946

Uitați și sursa,, :

http://www.infoarena.ro/job_detail/1199946?action=view-source

Vă rog,, ajutor..

[•valen.valentin]

ce e cu eroarea aceasta ce inseamna  :readthis:Blocked system call: (null).

[•eusebiu_gagea]

Buna ziua! Tot incerc de ceva timp sa fac prblema dar nu reusesc sa iau decat 10 pct. Am pus in coada direct toate pozitiile paznicililor. nu pot sa inteleg ce am gresit. Las si programul meu, in caz ca ma poate ajuta cineva.

Cod:

#include <fstream>
#define NV 4
#define Nmax 62500
using namespace std;
ifstream fin("muzeu.in");
ofstream fout("muzeu.out");
int a[252][252],n,k,p,u;
struct Pct{int x,y;};
Pct c[Nmax];
int dx[NV] = {-1,0,1,0};
int dy[NV] = {0,1,0,-1};

void citire();
void Lee();
void afisare();

int main()
{
    citire();
    Lee();
    afisare();
    return 0;
}

void citire()
{
    int i,j;
    char sir[252];
    fin>>n;
    fin.get();
    for(i=1; i<=n; i++)
    {
        fin.getline(sir,252);
        for(j=1; j<=n; j++)
        {
            if(sir[j-1]=='.')
                a[i][j]=-1;
            else if(sir[j-1]=='#')
                a[i][j]=-2;
            else
            {
                a[i][j]=0;
                c[u].x=i;
                c[u++].y=j;
            }
        }
    }
}

void Lee()
{
    Pct B,C;
    u--;
    int i;
    while(p<=u)
    {
        B.x=c[p].x;
        B.y=c[p].y;
        p++;
        for(i=0; i<NV; i++)
        {
            C.x=B.x+dx[i];
            C.y=B.y+dy[i];
            if(a[C.x][C.y]==-1)
            {
                a[C.x][C.y]=a[B.x][B.y]+1;
                u++;
                c[u].x=C.x;
                c[u].y=C.y;

            }
        }
    }
}

void afisare()
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            if(a[i][j]<0)
                fout<<a[i][j]<<" ";
            else
                fout<<" "<<a[i][j]<<" ";
        fout<<"\n";
    }
}

Editat de moderator: Încearcă să foloseşti tag-ul [code ] [ /code] atunci când vrei să inserezi fragmente din surse.

[•RaduToporan]

Solutia de 100p folosind algoritmul lui Lee:

#include <cstdio>

int i,j,n,sc,a[255][255];
int dx[]={0, 1, 0, -1};
int dy[]={1, 0, -1, 0};
struct coada
{
    int l,c;
};
coada c[66000];

void citire()
{
    int i,j;
    char s[255];
    freopen("muzeu.in","r",stdin);
    freopen("muzeu.out","w",stdout);
    scanf("%d",&n);
    sc=0;
    for (i=1; i<=n; i++)
    {
        scanf("%s",&s);
        for (j=0; j<=n-1; j++)
            if (s[j]=='#') a[j+1]=-1;
                else if (s[j]=='P')
                {
                    a[j+1]=1;
                    sc++;
                    c[sc].l=i;
                    c[sc].c=j+1;
                }
    }
}

void bordare()
{
    int i;
    for (i=0; i<=n+1; i++)
    {
        a

• =-1;

        a[n+1]=-1;
        a[0]=-1;
        a[n+1]=-1;
    }
}

void Lee()
{
    int i,ic=1;
    coada t,cx;
    while (ic<=sc)
    {
        t=c[ic];
        ic++;
        for (i=0; i<=3; i++)
        {
            cx.l=t.l+dx;
            cx.c=t.c+dy;
            if (a[cx.l][cx.c]==0)
            {
                sc++;
                c[sc].l=cx.l;
                c[sc].c=cx.c;
                a[cx.l][cx.c]=a[t.l][t.c]+1;
            }
        }
    }
}

void afisare()
{
    int i,j;
   for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
            printf("%d ",a[j]-1);
        printf("\n");
    }
}

int main()
{
    citire();
    bordare();
    Lee();
    afisare();
    return 0;
}

[•PinkiePie1189]

de ce e sursa goala si de ce merge

[•adriannord]

#include <fstream>
#include <climits>
#include <iomanip>
#include <queue>
using namespace std;

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

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

char a[250][250];
int c[250][250];
int n;
queue< pair <int, int> > Q;
int Ok (int I, int J);

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            {
                fin >> a[j];
                if (a[j] == 'P')
                    {
                        c[j] = 1;
                    }
            }


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (c[j] == 0)
                c[j] = INT_MAX;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (c[j] == 1)
                {
                    c[j] = 0;
                    Q.push({i, j});
                }

    int i, j, iv, jv;

    while(!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();

        for (int d = 1; d <= 4; d++)
        {
            iv = i + di[d];
            jv = j + dj[d];
            if (Ok(iv, jv) && c[iv][jv] > c[j] + 1)
            {
                c[iv][jv] = c[j] + 1;
                Q.push({iv, jv});
            }
        }
    }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (c[j] == INT_MAX)
                    c[j] = -1;

        for (int i = 1; i <= n; ++i, fout << endl)
            for (int j = 1; j <= n; ++j)
                fout << c[j] << ' ';


}

int Ok(int I, int J)
{
    if (I > n || J > n || I < 1 || J < 1)
        return false;
    if (a[J] == '#')
        return false;

    return true;
}
 ce nu e bine?

[•AndreiDelta]

Ma poate ajuta cineva!Am folosit Lee,dar mai mult de 30 puncte nu obtin deoarece raspunsul e incorect.


#include <fstream>
#include <queue>
#include <iostream>
using namespace std;
ifstream f("muzeu.in");
ofstream g("muzeu.out");
int OK();
int  n,k=0,dl[]={0,1,-1,0,0},dc[]={0,0,0,1,-1},M[251][251],x,y,x1,y1;
char litera;

queue <pair <int,int> > Q;
pair <int,int> P[251];
void Citire()
{
    f>>n; f.get();
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
    {
        f.get(litera);
        if(litera=='P') { Q.push(make_pair(i+1,j+1)); k++; }
        else
            if(litera=='#') M[i+1][j+1]=-2;
        if(j==n-1) {f.get(); }
    }

}

void Lee()
{  int l=0;
    while(!Q.empty())
    {
        x=Q.front().first;
        y=Q.front().second; l++;
        Q.pop();
        for(int i=1;i<=4;i++)
        {
            x1=x+dl;
            y1=y+dc;
            if(OK()!=0&&M

• [y]!=-3)

            {
                M[x1][y1]=M

• [y]+1;

                Q.push(make_pair(x1,y1));
            }
        }
        if(l<=k) M

• [y]=-3;

    }
}

int OK()
{
    if(M[x1][y1]!=0&&(x1>=1&&y1>=1&&x1<=n&&y1<=n)&&M[x1][y1]!=-2&&M

• [y]+1<M[x1][y1])

        return 1;
     if(M[x1][y1]==0&&(x1>=1&&y1>=1&&x1<=n&&y1<=n))
        return 1;
        return 0;
}

int main()
{
    Citire();
    Lee();
       for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
         {
             if(M[j]==0) M[j]=-1;
             if(M[j]==-3) M[j]=0;
             if(j<n) g<<M[j]<<" ";
             if(j==n) {  g<<M[j]; g<<'\n';  }
         }
    return 0;
}

[•AndreiDelta]

Ma poate ajuta cineva!Am folosit Lee,dar mai mult de 30 puncte nu obtin deoarece raspunsul e incorect.


#include <fstream>
#include <queue>
#include <iostream>
using namespace std;
ifstream f("muzeu.in");
ofstream g("muzeu.out");
int OK();
int  n,k=0,dl[]={0,1,-1,0,0},dc[]={0,0,0,1,-1},M[251][251],x,y,x1,y1;
char litera;

queue <pair <int,int> > Q;
pair <int,int> P[251];
void Citire()
{
    f>>n; f.get();
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
    {
        f.get(litera);
        if(litera=='P') { Q.push(make_pair(i+1,j+1)); k++; }
        else
            if(litera=='#') M[i+1][j+1]=-2;
        if(j==n-1) {f.get(); }
    }

}

void Lee()
{  int l=0;
    while(!Q.empty())
    {
        x=Q.front().first;
        y=Q.front().second; l++;
        Q.pop();
        for(int i=1;i<=4;i++)
        {
            x1=x+dl;
            y1=y+dc;
            if(OK()!=0&&M

• [y]!=-3)

            {
                M[x1][y1]=M

• [y]+1;

                Q.push(make_pair(x1,y1));
            }
        }
        if(l<=k) M

• [y]=-3;

    }
}

int OK()
{
    if(M[x1][y1]!=0&&(x1>=1&&y1>=1&&x1<=n&&y1<=n)&&M[x1][y1]!=-2&&M

• [y]+1<M[x1][y1])

        return 1;
     if(M[x1][y1]==0&&(x1>=1&&y1>=1&&x1<=n&&y1<=n))
        return 1;
        return 0;
}

int main()
{
    Citire();
    Lee();
       for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
         {
             if(M[j]==0) M[j]=-1;
             if(M[j]==-3) M[j]=0;
             if(j<n) g<<M[j]<<" ";
             if(j==n) {  g<<M[j]; g<<'\n';  }
         }
    return 0;
}