Imprimă pagina - 1215 Pescari

Titlul: 1215 Pescari
Scris de: Andrei Grigorean din Octombrie 17, 2011, 16:00:56

Aici puteÅ£i discuta despre problema Pescari (http://infoarena.ro/problema/pescari).

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Boaca Cosmin din Octombrie 17, 2011, 21:29:01

Complexitatea ceruta e O(N * M) ?

Titlul: RÄƒspuns: 1215 Pescari
Scris de: George Marcus din Octombrie 17, 2011, 23:03:22

Citat din mesajul lui: Boaca Cosmin din Octombrie 17, 2011, 21:29:01

Complexitatea ceruta e O(N * M) ?

Da.

Cu ce ne ajuta acel P ? :)

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Gabriel Bitis din Octombrie 18, 2011, 12:53:34

Nu prea ajuta P.

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Boaca Cosmin din Octombrie 18, 2011, 18:31:28

Daca se poate face N * M cu lee va rog frumos lasati-mi un hint ... Eu am facut 100 cu o dinamica dar fol 20mb memorie pe testul maxim . Multumesc anticipat .

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Gabriel Bitis din Octombrie 18, 2011, 18:35:22

Ideea ta de dinamica e interesanta, si ruleaza destul de repede :)
Ca sa faci cu Lee poti introduce in coada toate terenurile acoperite cu apa, si vezi care e distanta minima de la acele terenuri la oricare alt punct de pe harta. Ideea e sa faci un singur Lee.

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Boaca Cosmin din Octombrie 18, 2011, 18:39:17

Pai asta nu ar fi similar cu a face lee din fiecare teren acoperit cu apa ? Sau le introduc in coada pe toate din prima ? Daca le introduc din prima in coada pe toate nu ar trebui sa vizitez fiecare celula din matrice kte odata pt fiekre punct din coada ca sa asigur optimalitatea distantelor sau distanta ramane optima si daca vizitez fiecare patrat doar pentru primul drum care il contine ?

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Gabriel Bitis din Octombrie 18, 2011, 18:46:17

Daca le introduci pe toate din prima, vei verifica prima data vecinii acestor puncte care nu sunt terenuri acoperite cu apa si vei introduce in coada puncte cu distante = 1. Cand vei ajunge sa procesezi aceste puncte, nu mai are rost sa verifici punctele bagate deja in coada pentru ca ai calculate deja distantele pentru ele, deci va urma sa adaugi punctele de la distanta 2, s.a.m.d pana bagi toate punctele in coada.

Poti observa ca un punct intra o singura data in coada din cauza ordinii in care le pargurgi. Nu se va intampla sa ajungi la un punct cu distanta X, sa'l bagi in coada, apoi sa ajungi la alt punct cu distanta Y (Y < X) pe care sa'l adaugi in coada, iar al doilea punct sa te determine sa recalculezi distanta primului punct.

Titlul: RÄƒspuns: 1215 Pescari
Scris de: FMI Ciprian Olariu din Octombrie 18, 2011, 18:57:27

Citat din mesajul lui: Gabriel Bitis din Octombrie 18, 2011, 18:46:17

Asta din cauza ca distanta dintre oricare 2 celule vecine e 1 si deci este exact la fel ca la un BFS folosit pe un graf neorientat fara costuri pe muchii pentru a afla distanta(costul) minima. Daca ar fi fost distanta dintre 2 campuri vecine variabila,in functie de vreun numar continut de acel camp din matrice,atunci ar fi fost de ajutor ca optimizarea folosirea unei cozi de prioritati (sortata dupa distante minime),in loc de coada obisnuita :thumbup:

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Cristian Lambru din Octombrie 18, 2011, 19:29:55

Ca sa intelegi mai bine cum merge Lee-ul cu toate elementele introduse de la inceput in coada incearca sa faci problema Muzeu (http://infoarena.ro/problema/muzeu) :D .

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Boaca Cosmin din Octombrie 19, 2011, 19:32:38

Va multumesc la toti 3 pentru raspunsurile voastre . Am inteles acum de ce merge corect ideea de a baga toate terenurile in coada de la inceput :D .

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Tudor Tiplea din Octombrie 20, 2011, 18:01:10

Salut! Am implementat solutia cu algoritmul lui Lee,am pus de la inceput in coada dar iau 90 de puncte,pe testul 7 imi dai Incorect ](*,) .Stau de nu stiu cat timp dar nu imi dau seama care este problema. O fi vreun caz special?

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Lodoaba Sorin din Octombrie 23, 2011, 11:36:39

pot sa fie 2 pescari pe acceasi balta ?

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Simoiu Robert din Octombrie 23, 2011, 11:49:30

Dupa cum zice si in enunt, adica sa aflam drumul minim al fiecarui pescar pana la cea mai apropiata balta, atunci merge oricati pescari pe aceeasi balta :ok:.

Titlul: RÄƒspuns: 1215 Pescari
Scris de: FMI Razvan Birisan din Ianuarie 03, 2013, 16:58:36

Am luat 40p. :fool:
???

Titlul: RÄƒspuns: 1215 Pescari
Scris de: FMI Paun Matei din Ianuarie 05, 2013, 00:43:13

vezi ca dimensiunile matricei nu trebuie sa fie exacte pune 1001
si incearca sa mai reduci prin program fara sa pui atatea if-uri
faci 2 vectori de coordonare dx si dy cu cele 8 sau 4 directii ( adica daca mergi in nord pui dx [ 1 ] = -1 si dy [ i ] = 0 ) si faci un for in care verifici daca lin + dx [ i ] si col + dy [ i ] :) dar trebuie sa pui toate conditiile alea cu n>lin >0 si n>col >0 etc ..
Sper sa te ajute :D

Titlul: RÄƒspuns: 1215 Pescari
Scris de: FMI Razvan Birisan din Ianuarie 05, 2013, 19:49:08

O sÄƒ scriu codul din nou...
Mersi pentru sfaturi. :)

Titlul: RÄƒspuns: 1215 Pescari
Scris de: Cosmin Rusu din Februarie 10, 2013, 16:31:00

Cod:

#include<fstream>
#include<iostream>
using namespace std;

int a[1005][1005],i,j,ok,u,p,P,q[3][10005],c,d,y,m,sir[3][10005],maxi,l[1005][1005],n,k=0;
ifstream fin("pescari.in");
ofstream g("pescari.out");

void init()

{

     //citim datele din fisierul pescari.in
     fin>>n>>m>>P;
   //  cout<<n;
      for(i=1;i<=n;i++)
             for(j=1;j<=m;j++)
            { fin>>a[i][j];
              l[i][j]=0;
              if(a[i][j]==2) {l[i][j]=0;k++;sir[1][k]=i;sir[2][k]=j;}
            }
             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, y;
     p=0;u=0;
     p=0;
     u=k;
     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]==0 || a[x-1][y]==1)
       if((l[x-1][y]>l[x][y]+1||l[x-1][y]==0))
       {
                                       l[x-1][y]=l[x][y]+1;
       intr(x-1,y);

      }

     //
      if(x<n)
       if(a[x+1][y]==0 || a[x+1][y]==1)
        if(l[x+1][y]>l[x][y]+1||l[x+1][y]==0)
        {l[x+1][y]=l[x][y]+1;
         intr(x+1,y);

         }

    if(y>1)
     if(a[x][y-1]==0 || a[x][y-1]==1)
           if(l[x][y-1]>l[x][y]+1 || l[x][y-1]==0)
           {l[x][y-1]=l[x][y]+1;
                                  intr(x,y-1);

                                  }
    if(y<m)
     if(a[x][y+1]==0 || a[x][y+1]==1)
      if(l[x][y+1]>l[x][y]+1||l[x][y+1]==0)
    {l[x][y+1]=l[x][y]+1;
    intr(x,y+1);

    }
    if(y<m && x<n)
     if(a[x+1][y+1]==0 || a[x+1][y+1]==1)
      if(l[x+1][y+1]>l[x][y]+1||l[x+1][y+1]==0)
    {l[x+1][y+1]=l[x][y]+1;
    intr(x+1,y+1);}


    if(y>1 && x<n)
     if(a[x+1][y-1]==0 || a[x+1][y-1]==1)
      if(l[x+1][y-1]>l[x][y]+1||l[x+1][y-1]==0)
    {l[x+1][y-1]=l[x][y]+1;
    intr(x+1,y-1);}


    if(y<m && x>1)
     if(a[x-1][y+1]==0 || a[x-1][y+1]==1)
      if(l[x-1][y+1]>l[x][y]+1||l[x-1][y+1]==0)
    {l[x-1][y+1]=l[x][y]+1;
    intr(x-1,y+1);}


    if(y>1 && x>1)
     if(a[x-1][y-1]==0 || a[x-1][y-1]==1)
      if(l[x-1][y-1]>l[x][y]+1||l[x-1][y-1]==0)
    {l[x-1][y-1]=l[x][y]+1;
    intr(x-1,y-1);

    }

}

}
void scriere()
{

      for(i=1;i<=n;i++)
                       for(j=1;j<=m;j++)
                                        if(a[i][j]==1)
                                           g<<l[i][j]<<"\n";
}
int main()
{

    init();
    for(i=1;i<=k;i++) {
        q[1][i]=sir[1][i];
        q[2][i]=sir[2][i];
    }
    lee();
     scriere();

    return 0;
}

Sursa mea ia 50 de puncte. Pe restul testelor avand Incorect. As ramane profund indatorat daca cineva mi-ar explica unde si de ce gresesc :). Numai bine :peacefingers:!

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Octombrie 17, 2011, 16:00:56