Поиск кратчайшего пути в лабиринте на Си

[EpicFashion]

Завтра зачёт, поздновато спохватился, короче есть прога (препод её уже видел, так что новая не пойдёт), она работает, но не совсем как надо и не полностью. Если кто охуенно шарит в Си помогите исправить.

Тема актуальна часов так 5(до зачёта)

 

 

Собственно сам код:

Нужно чтобы он не только все пути считал, но показывал из них путь из точки 88 в точку 99 самый короткий и один.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define n 10
int mas[n][n];
void shag(int k, int m,int t)
{
        
        if(k-1>=0){
                if((mas[k-1][m]==0)){
                        mas[k-1][m]=t+1;
                        shag(k-1,m,t+1);
                    }else 
                                if((mas[k-1][m]>t)/*&&(mas[k-1][m]!=99)*/){
                                        mas[k-1][m]=t+1;
                                        shag(k-1,m,t+1);
                                }
        }
        
        if(k+1<n){
                if((mas[k+1][m]==0)){
                        mas[k+1][m]=t+1;
                        shag(k+1,m,t+1);
                    }else 
                                if((mas[k+1][m]>t)/*&&(mas[k+1][m]!=99)*/){
                                        mas[k+1][m]=t+1;
                                        shag(k+1,m,t+1);
                                }
        }
        
        if(m-1>=0){
                if((mas[k][m-1]==0)){
                        mas[k][m-1]=t+1;
                        shag(k,m-1,t+1);
                    }else 
                                if((mas[k][m-1]>t)/*&&(mas[k][m-1]!=99)*/){
                                        mas[k][m-1]=t+1;
                                        shag(k,m-1,t+1);
                                  }
        }
        
        if(m+1<n){
                if((mas[k][m+1]==0)){
                        mas[k][m+1]=t+1;
                        shag(k,m+1,t+1);
                    }else 
                                if((mas[k][m+1]>t)/*&&(mas[k][m+1]!=99)*/){
                                        mas[k][m+1]=t+1;
                                        shag(k,m+1,t+1);
                                }
        }
}
void shagnazad(int v,int u,int r)
{
        if((v-1>=0)&&(mas[v-1][u]==r-1))
                {mas[v][u]=1; shagnazad(v-1,u,r-1);}
        if((v+1<n)&&(mas[v+1][u]==r-1))
                {mas[v][u]=1; shagnazad(v+1,u,r-1);}
        if((u-1>=0)&&(mas[v][u-1]==r-1))
                {mas[v][u]=1; shagnazad(v,u-1,r-1);}
        if((u+1<n)&&(mas[v][u+1]==r-1))
                {mas[v][u]=1; shagnazad(v,u+1,r-1);}

}
void main()
{
        int i,j;
        FILE *f;
        f=fopen("labyrinth.txt","r");
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        fscanf(f,"%d",&mas[i][j]);
        fclose(f);
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        if(mas[i][j]==88)
                                shag(i,j,0);

        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        if(mas[i][j]==99)
                        {
                                if((i-1>=0)&&(mas[i-1][j]!=-1))
                                        shagnazad(i-1,j,mas[i-1][j]);
                                if((i+1<n)&&(mas[i+1][j]!=-1))
                                        shagnazad(i+1,j,mas[i+1][j]);
                                if((j-1>=0)&&(mas[i][j-1]!=-1))
                                        shagnazad(i,j-1,mas[i][j-1]);
                                if((j+1<n)&&(mas[i][j+1]!=-1))
                                        shagnazad(i,j+1,mas[i][j+1]);
                        }

        f=fopen("doroga.txt","w");
        for(i=0;i<n;i++)
        {   
                fprintf(f,"\n""\n");
                printf("\n""\n");
                for(j=0;j<n;j++)
                {
                fprintf(f,"%d  ",mas[i][j]);
                printf("%d  ",mas[i][j]);
                
                }
        }
        fclose(f);
        getch();
}

 

 

Это то что должно быть в labyrinth.txt

0  -1 -1 -1 88 -1 -1 -1  0  0
0   0  0 -1  0  0 -1  0  0  0
0  -1 -1 -1  0  0 -1 -1 -1  0
0   0  0  0  0  0  0  0 -1  0
0  -1  0 -1 -1 -1  0  0  0  0
0  -1  0 -1 -1 -1  0 -1 -1 -1
-1 -1  0 -1 -1 -1  0  0 -1  0
0  -1  0  0  0  0  0  0  0  0
0  -1  0 -1 -1  0 -1 -1 -1  0
0   0  0 -1  0  0  0 99  0  0

Спасибо за помощь

[iKrivetko]

Это не C :NYbuba:

[EpicFashion]

а что же это? то что это не C++ эт точно

 

а ну ок conio.h это не си, но оно нужно для getch(), больше не для чего, убераем getch(), убераем conio.h, вот тебе и чистый Си

[iKrivetko]

Был неправ, видимо. :NYhmm:

Anyway, знание языка как такового тут не принципиально по большому счету.

[EHOME]

Это не C :NYbuba:

смешнявочка

[EpicFashion]

я знаю что тут не так, но не могу реализовать

когда находит 99, он его затирает след по номеру шагом, и обратно уже не топает, поэтому я ставил в шаге вперёд

&&(mas[k-1][m]!=99)

но тогда он вообще глупить начинает, обрывает поиск пути ещё на начале

 

[EHOME]

я может потом посмотрю, у меня визуал вчера крашнулся, надо переустановить

[iKrivetko]

Что есть int t в шаге?

[EpicFashion]

по возможности до 9 утра по Москве посмотри, это и то уже на учёбе придётся сразу копипастить и сдавать

вот если что выходная строка:

10  -1   -1  -1   2  -1  -1  -1  14  13  

9   10   11  -1   1   2  -1  14  13  12  

8   -1   -1  -1   2   3  -1  -1  -1  11  

7    6    5   4   3   4   5   6  -1  10  

8   -1    6  -1  -1  -1   6   7   8   9  

9   -1    7  -1  -1  -1   7  -1  -1  -1  

-1  -1    8  -1  -1  -1   8   9  -1  13  

15  -1    9  10  11  10   9  10  11  12  

14  -1   10  -1  -1  11  -1  -1  -1  13  

13  12   11  -1  13  12  13  14  15  14  

 

[EpicFashion]

Что есть int t в шаге?

"t" - это сам номер шага, который вписывается в массив

аналогично "r" в шаге назад это вычитания шага от максимального чтобы вернуться в точку 88, но это то и не работает