Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Labirint  (Citit de 3857 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
reking
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« : Februarie 25, 2013, 22:52:12 »

Am incercat sa rezolv o problema cu un labirint (mai exact https://infoarena.ro/algoritmul-lee prima), dar imi intra in bucla infinita.
Problema este partial rezolvata...adica am incercat s-o fac pana la afisarea celei de a 2-a matrici (in care am retinut nr de pasi)
Sugestii?
Sursa :
Cod:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("labirint.in");
ofstream g("labirint.out");
void bordare (int m, int n,int a[100][100])
{
    int k;
    for (k=0;k<=n;k++)
    {
        a[0][k]=0;
    }
    for (k=0;k<=n;k++)
    {
        a[n+1][k]=0;
    }
    for (k=n+1;k>=1;k--)
    {
        a[k][m+1]=0;
    }
    for (k=m+1;k>=1;k--)
    {
        a[k][0]=0;
    }
}
int main ()
{
    int a[100][100],b[100][100]={0},d1[]={0,1,0,-1},d2[]={-1,0,1,0},l[1000],c[1000],x,y,x1,y1,i,j,m,n,k;
    f>>m>>n;
    for (i=1;i<=m;i++)
    {
        for (j=1;j<=n;j++)
        {
            f>>a[i][j];
        }
    }
    bordare (m,n,a);
    for (i=1;i<=m;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (a[i][j]==-1) {l[0]=i;c[0]=j;}
        }
    }
    b[l[0]][c[0]]=a[l[0]][c[0]];
    i=j=0;
    while (i<=j)
    {
        x=l[i];
        y=c[i];
        for (k=0;j<4;k++)
        {
            x1=x+d1[k];
            y1=y+d2[k];
            if (a[x1][y1]!=0)
            {
                if (b[x1][y1]==0)
                {
                    b[x1][y1]=a[x1][y1]+b[x][y];
                    j++;
                    l[j]=x1;
                    c[j]=y1;
                }
                else if (b[x][y]+a[x1][y1]<b[x1][y1])
                {
                    b[x1][y1]=b[x][y]+a[x1][y1];
                    j++;
                    l[j]=x1;c[j]=y1;
                }
            }
        }
        i++;
    }
    for (i=0;i<=m+1;i++)
    {
        for (j=0;j<=n+1;j++)
        {
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
}
PS:am modificat putin enuntul problemei (am inversat 0 cu 1)
adica testul este cam asa :
5 5
0 0 0 0 0
0 1 1 1 -1
0 1 1 0 0
0 1 1 0 0
0 1 0 0 0
-si se poate merge doar pe 1
« Ultima modificare: Februarie 25, 2013, 23:02:10 de către C Bogdan » Memorat
darkseeker
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #1 : Februarie 26, 2013, 13:53:53 »

O prima problema ar fi ca in for-ul unde parcurgi vectorul de directii ai
Cod:
for (k = 0; j < 4; k++)
si ar trebui sa ai k < 4, si cred ca in functia de bordare ar trebui sa modifici k >= 1 in k >= 0.
Memorat
reking
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #2 : Februarie 26, 2013, 14:18:59 »

Multumesc! Tongue
Neatentia asta...
Bun...momentan stiu ca algoritmul merge binisor dar mai am o eroare.
Testul de iesire este:
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 2 1 2 -1 0
0 0 3 2 0 0 0
0 0 4 3 0 0 0
0 0 5 0 0 0 0
0 0 0 0 0 0 0
Deci...la inceput e ceva gresit, deoarece pe parcurs vad ca merge.
Test de iesire bun:
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 3 2 1 -1 0
0 0 4 3 2 0 0
0 0 5 4 0 0 0
0 0 6 0 0 0 0
0 0 0 0 0 0 0
EDIT:
Gata am rezolvat Very Happy :
Problema era de la acel "-1" si pentru rezolvare am schimbat randul
b[l[0]][c[0]]=a[l[0]][c[0]];
cu
b[l[0]][c[0]]=a[l[0]][c[0]]=0;
(in speranta ca va mai avea cineva nevoie Smile )
« Ultima modificare: Februarie 26, 2013, 14:40:39 de către C Bogdan » Memorat
reking
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #3 : Februarie 27, 2013, 10:49:57 »

Bun....acum am alta problema Very Happy
Algoritmul merge doar pentru matrice patratica!!!
Solutii??? Very Happy
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines