114 Muzeu

[•zeroblitz36]

Moamah dar ce zgarcit este atunci cand verifica solutia
Cand folosesc printf("%3d",v[j]); imi da 0 puncte
Dar cand folosesc printf("%d " v[j]); mia dat 100

Trebuie sa specifice ca intre numere trebuie sa fie doar un spatiu, eu am pus cu format ca era mai aranjat asa.

[•SpiderMan]

Foloseste [ i ] , pentru ca el inseamna scris italic. Apoi in enunt scrie asa :

In fisierul muzeu.out veti afisa N linii, fiecare din ele continand N numere intregi (separate prin spatii).

[•chibicitiberiu]

Iau doar 60 puncte si nu imi dau seama de ce...

Am implementat Lee, si culmea... cu coada de 1000*500 elemente iau 50 pct (5 incorecte);
cu coada 1000*1000 iau 60 puncte (4 incorecte)
cu coada mai lunga incep sa iau TLE.

Cu toate ca am pus o functie "Purge" care sa stearga elem folosite cand se umple.

Cod:

#define DEBUG 0
#define MAXSTACK 1000*1000
#include<fstream>
#include<cstdlib>
#if DEBUG==1
#include<iostream>
#endif

using namespace std;


class Point
{
public:
    short X, Y;

    Point() { X = Y = 0; }
    Point(short x, short y) { X = x; Y = y; }

    Point operator+ (Point a)
    {
        return Point(a.X + X, a.Y + Y);
    }
    Point operator- (Point a)
    {
        return Point(X - a.X, Y - a.Y);
    }
    Point* operator= (const Point* a)
    {
        this->X = a->X;
        this->Y = a->Y;
        return this;
    }

#if DEBUG==1
    friend ostream& operator<<(ostream& output, const Point &p)
    {
        output<<p.X<<","<<p.Y;
        return output;
    }
#endif
};

class PointStep : public Point
{
public:
    short Step;

    PointStep() { X = Y = 0; }
    PointStep(short x, short y) { X = x; Y = y; }
    PointStep(short x, short y, int step) { X = x; Y = y; Step = step; }
    PointStep(Point w, int step) { X = w.X; Y = w.Y; Step = step; }

    PointStep operator+ (PointStep a)
    {
        return PointStep(a.X + X, a.Y + Y);
    }

    Point operator+ (Point a)
    {
        return Point(a.X + X, a.Y + Y);
    }

    PointStep operator- (PointStep a)
    {
        return PointStep(X - a.X, Y - a.Y);
    }

    Point operator- (Point a)
    {
        return Point(a.X + X, a.Y + Y);
    }

    PointStep* operator= (const PointStep* a)
    {
        this->X = a->X;
        this->Y = a->Y;
        return this;
    }
};

const Point Directions[4] = {Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0) };

int Map[260][260];
short MapSize;

PointStep Stack[MAXSTACK];
int StackSize, StackPos;


inline void Purge()
{
    for (int i = StackPos; i < StackSize; i++)
        Stack[i-StackPos] = Stack[i];

    StackPos = 0;
    StackSize -= StackPos;
}

inline void StackAdd(Point w, int step)
{
    Stack[StackSize++] = PointStep(w, step);

    if (StackSize >= MAXSTACK-2) Purge();
}

//**** Implementations of ReadFile / WriteFile
// ...
// ****

inline bool Okay (Point w, int pas)
{
    if (w.X < 0 || w.Y < 0 || w.X >= MapSize || w.Y >= MapSize) return false;
    if (Map[w.X][w.Y] == -1) return true;
    if (Map[w.X][w.Y] > pas) return true;

    return false;
}

void Lee()
{
    Point d;
    int pas = 0;

    while (StackPos < StackSize) {
        pas = Stack[StackPos].Step;
        for (int direction = 0; direction < 4; direction++)
        {
            d = Stack[StackPos] + Directions[direction];

            if (Okay(d, pas))
            {
                StackAdd(d, pas+1);
                Map[d.X][d.Y] = pas+1;
            }
        }

        StackPos++;
    }
}


int main()
{
    ReadFile("muzeu.in");
    Lee();
    WriteFile("muzeu.out");

    return 0;
}

[•SpiderMan]

Cel mai bine ar fi sa utilizezi coada dinamica din STL.

[•chibicitiberiu]

Cel mai bine ar fi sa utilizezi coada dinamica din STL.

Merci de sfat.

Am incercat si asa, dar tot 60 pct iau. Primesc TLE la testul 6, si Incorect  la 7 8 9

[•SpiderMan]

Ai folosit <queue> si .pop, respectiv .push ?

[•chibicitiberiu]

Ai folosit <queue> si .pop, respectiv .push ?

Da!

Aici este sursa noua:

Cod:

#define DEBUG 0
#define MAXSTACK 1000*1000
#include<fstream>
#include<cstdlib>
#include<queue>
#if DEBUG==1
#include<iostream>
#endif

using namespace std;


class Point
{
public:
    short X, Y;

    Point() { X = Y = 0; }
    Point(short x, short y) { X = x; Y = y; }

    Point operator+ (Point a)
    {
        return Point(a.X + X, a.Y + Y);
    }
    Point operator- (Point a)
    {
        return Point(X - a.X, Y - a.Y);
    }
    Point* operator= (const Point* a)
    {
        this->X = a->X;
        this->Y = a->Y;
        return this;
    }

#if DEBUG==1
    friend ostream& operator<<(ostream& output, const Point &p)
    {
        output<<p.X<<","<<p.Y;
        return output;
    }
#endif
};

class PointStep : public Point
{
public:
    short Step;

    PointStep() { X = Y = 0; }
    PointStep(short x, short y) { X = x; Y = y; }
    PointStep(short x, short y, int step) { X = x; Y = y; Step = step; }
    PointStep(Point w, int step) { X = w.X; Y = w.Y; Step = step; }

    PointStep operator+ (PointStep a)
    {
        return PointStep(a.X + X, a.Y + Y);
    }

    Point operator+ (Point a)
    {
        return Point(a.X + X, a.Y + Y);
    }

    PointStep operator- (PointStep a)
    {
        return PointStep(X - a.X, Y - a.Y);
    }

    Point operator- (Point a)
    {
        return Point(a.X + X, a.Y + Y);
    }

    PointStep* operator= (const PointStep* a)
    {
        this->X = a->X;
        this->Y = a->Y;
        return this;
    }
};

const Point Directions[4] = {Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0) };

int Map[260][260];
short MapSize;

queue<PointStep> Queue;

void ReadFile(char* fileName)
{
    char buffer[250];
    ifstream in (fileName);

    in>>MapSize;
    in.getline(buffer, 250, '\n');

    for (short x=0; x < MapSize; x++)
    {
        in.getline(buffer, 250, '\n');
        for (short y=0; y < MapSize; y++)
            switch (buffer[y])
            {
                case '#': Map[x][y] = -2; break;
                case 'P': Map[x][y] = 0; Queue.push(PointStep(x, y, 0)); break;
                default: Map[x][y] = -1; break;
            }
    }

    in.close();
}

void WriteFile(char* fileName)
{
    ofstream out (fileName);

    for (int x=0; x< MapSize; x++, out<<endl)
        for (int y=0; y<MapSize; y++)
            out<<Map[x][y]<<" ";
}

inline bool Okay (Point w, int pas)
{
    if (w.X < 0 || w.Y < 0 || w.X >= MapSize || w.Y >= MapSize) return false;
    if (Map[w.X][w.Y] == -1) return true;
    if (Map[w.X][w.Y] > pas) return true;

    return false;
}

void Lee()
{
    Point d;
    int pas = 0;

    while (!Queue.empty()) {
        PointStep temp = Queue.front();
        pas = temp.Step;
        for (int direction = 0; direction < 4; direction++)
        {
            d = temp + Directions[direction];

            if (Okay(d, pas))
            {
                Queue.push(PointStep(d, pas+1));
                Map[d.X][d.Y] = pas+1;
            }
        }

        Queue.pop();
    }
}


int main()
{
    ReadFile("muzeu.in");
    Lee();
    WriteFile("muzeu.out");

    return 0;
}

[•VisuianMihai]

cum pot sa aflu nodurile ce pot fi atinse de paznici? Ma refer la parcurgerea in latime

[•caen1]

Eu am incercat sa o fac cu un Lee implementat cu o coada (sunt a 10-a si nu stiu altfel) si iau doar 50, pe restul iese din timp. Retin coordonatele paznicilor intr-un struct si pentru fiecare paznic fac Lee. Gresesc undeva, sau Lee-ul pe care il fac eu nu ar trebui sa intre in timp?

[•SpiderMan]

Deci in acea coada bagi toate coordonatele paznicilor, si faci un singur lee, adica lee-ul normal il faci cu un singur paznic bagat, aici ii bagi pe toti si faci un lee, si atat .

[•sharky12592]

Buna ziua , imi poate spune cineva cum fac matricea de adiacenta pentru a rezolva problema cu parcurgerea in latime ? Multumesc.

[•mathboy]

Consideri ca matricea este un graf in care ai muchii din (i, j) in { (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1) }, exceptiile fiind casutele avand caracterul '#' , in care nu poti trasa muchii din / spre acea pozitie.

[•sharky12592]

Ok , deci casutele cu caracterul " # " le pot considera noduri izolate . Multumesc.

[•alexalbu95]

Cine imi poate spune cum as putea face programul meu mai rapid, sau unde gresesc? Eu am facut cu Lee pentru ca nu am invatat grafuri.

[•cosminionut]

Nu iau TLE , dar am probleme la 6 teste cu WA.
Daca ar fi cineva dispus sa ma ajute as fi mai mult decat bucuros  .

[•TheNechiz]

Iau TLE pe 2 teste.

Plec de la fiecare paznic și fac Lee.

[•PlayLikeNeverB4]

Pleaca de la inceput din toti paznicii (ii bagi in coada).

[•TheNechiz]

Cod:

    for( i = 0 ; i <= k ; ++i )
    {
        c[0].x = p[i].r;
        c[0].y = p[i].t;
        for( g = 0 , ind = 0 ; g <= ind ; ++g )
...

http://infoarena.ro/job_detail/827451

iau 80p.

[•PlayLikeNeverB4]

Nu m-ai inteles.
Ii bagi in coada pe toti de la inceput. Cam asa:

Cod:

for(i = 0; i <= k; i++) {
   c[i].x = p[i].r;
   c[i].y = p[i].t;
}
ind = k;

si apoi faci parcurgerea.

Si atunci cand gasesti pe cineva cu distanta mai mica, verifica daca nu e introdus deja in coada ca sa nu bagi de mai multe ori aceeasi celula.

[•TheNechiz]

Merci pentru ajutor.

Acum am înțeles.

[•CosminRusu]

Cod:

//Problema muzeu
#include<fstream>
#include<iostream>
using namespace std;
  
int a[251][251],i,j,ok,u,p,q[3][20001],c,d,y,sir[3][100000],maxi,l[251][251],n,k=0;
ifstream fin("muzeu.in");
ofstream g("muzeu.out");
  
void init()
  
{
       
     //citim datele din fisierul muzeu.in
     fin>>n;
   //  cout<<n;
     char c;
      for(i=1;i<=n;i++)
             for(j=1;j<=n;j++)
            { fin>>c;
             if (c=='.')
             { a[i][j]=1;
              l[i][j]=-1;
              }
             else if (c=='P') {a[i][j]=10;k++;sir[1][k]=i;sir[2][k]=j;}
                                else l[i][j]=-2;
                                }
             fin.close();
          
           
}
//instroduc linia c si col d in coada
void intr(int c,int d)
{
     u=u+1;
      if(u>20000)
       u=1;
         
       q[1][u]=c;
       q[2][u]=d;
} 
//extrag un element din coada
void extr(int &c,int &d)
{
     p=p+1;
     if(p>20000)
     p=1;
       
     c=q[1][p];
     d=q[2][p];
}
  
//algoritmul LEE
void lee(int x,int y)
{
     p=0;u=0;
     intr(x,y);
     while(p!=u)
    { extr(x,y);
     
   //vecinul de sus 
   //daca are inaltime mai mare si numarul de catarari mai mic atunci
   //actualizez numarul de catarari cu l[x][y]+1
     if(x>1)
       
      if(a[x-1][y]==1)
       if(l[x-1][y]>l[x][y]+1||l[x-1][y]==-1)
       {l[x-1][y]=l[x][y]+1;
       intr(x-1,y);
  
      }
       
     //
      if(x<n)
       if(a[x+1][y]==1)
        if(l[x+1][y]>l[x][y]+1||l[x+1][y]==-1)
        {l[x+1][y]=l[x][y]+1;
         intr(x+1,y);
   
         }
  
    if(y>1)
     if(a[x][y-1]==1)      
           if(l[x][y-1]>l[x][y]+1||l[x][y-1]==-1)
           {l[x][y-1]=l[x][y]+1;
                                  intr(x,y-1);
          
                                  }
    if(y<n)
     if(a[x][y+1]==1)
      if(l[x][y+1]>l[x][y]+1||l[x][y+1]==-1)
    {l[x][y+1]=l[x][y]+1;
    intr(x,y+1);
    
    }
      
}
  
}
void scriere()
{ 
  
             
        
      for(i=1;i<=n;i++)
             {g<<"\n";
                          for(j=1;j<=n;j++)
              g<<l[i][j]<<" ";}
     maxi=-1;
    //  for(i=1;i<=n;i++)
     //  for(j=1;j<=n;j++)
       // if(l[i][j]>maxi)
       // maxi=l[i][j];
    
}
int main()
{
   
    init();
    for(i=1;i<=k;i++)
     lee(sir[1][i],sir[2][i]);
      
     scriere();
    
    return 0;
}

Ma puteti ajuta si pe mine sa vad ce gresesc aici ?  Sursa mea nu trece doua dintre teste cu textul Time limit exceeded. Multumesc anticipat !

[•SebiSebi]

Incearca sa bagi toti paznicii in coada de la inceput si pe urma ruleaza parcurgerea. 

[•CosminRusu]

Cred ca fac asta in functia init . Nu am prea inteles ce vroiai sa zici, poti fi mai explicit te rog  ?

[•visanr]

Tu faci lee din fiecare paznic (liniile 120 si 121). Ca sa mearga mai repede, bagi in coada de la inceput toti paznicii si faci lee o singura data (adica la linia 57 introduci toti cei k paznici in coada).

[•SebiSebi]

Exact.