1215 Pescari

[•wefgef]

Aici puteţi discuta despre problema Pescari.

[•darkseeker]

Complexitatea ceruta e O(N * M) ?

[•PlayLikeNeverB4]

Complexitatea ceruta e O(N * M) ?

Da.

Cu ce ne ajuta acel P ?

[•gabitzish1]

Nu prea ajuta P.

[•darkseeker]

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 .

[•gabitzish1]

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.

[•darkseeker]

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 ?

[•gabitzish1]

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.

[•scipianus]

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.

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  

[•maritim]

Ca sa intelegi mai bine cum merge Lee-ul cu toate elementele introduse de la inceput in coada incearca sa faci problema Muzeu .

[•darkseeker]

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 .

[•tzipleatud]

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?

[•lsorin_94]

pot sa fie 2 pescari pe acceasi balta ?

[•SpiderMan]

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  .

[•TheNechiz]

Am luat 40p.

[•paunmatei7]

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

[•TheNechiz]

O să scriu codul din nou...
Mersi pentru sfaturi.

[•CosminRusu]

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  !