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 :
#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