Выход из лабиринта

[karamelka87]

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

#include <stdio.h>
#define MAX_NUMBERS 10

int labirint[MAX_NUMBERS][MAX_NUMBERS];
int exitX, exitY, flag;

int LegalStep( int x, int y) 
{
  if ((x < 0)||(y < 0)||(x >= MAX_NUMBERS)||(y >= MAX_NUMBERS)) 
     return 0;
  return 1;
} 

int ExitLabirint(int x, int y)
{ 
   labirint[x][y] = 2;
   
   if ((labirint[exitX][exitY] == 2))
      {
      flag = 1;
      return 0;
      }  
   else
   {
      if ((LegalStep(x+1,y)) && (labirint[x+1][y] == 0))
         ExitLabirint (x+1,y);
   
      if ((LegalStep(x,y+1)) && (labirint[x][y+1] == 0))
         ExitLabirint (x, y+1);
   
      if ((LegalStep(x-1,y)) && (labirint[x-1][y] == 0))
         ExitLabirint (x-1, y);
   
      if ((LegalStep(x,y-1)) && (labirint[x][y-1] == 0))
         ExitLabirint (x, y-1);       
   }    
}

int main()
{
   int x, y;   
   int labirint[MAX_NUMBERS][MAX_NUMBERS] = 
                      { {0,0,0,0,0,0,0,0,0,0},
                        {1,1,1,1,0,0,1,1,1,0},
                        {1,1,1,1,0,0,1,1,1,0},
                        {1,1,1,1,0,0,1,1,1,0},
                        {1,1,1,1,0,0,1,1,1,0},
                        {0,0,0,0,0,0,1,1,1,0},
                        {0,1,1,1,1,1,1,1,1,0},
                        {0,1,1,1,1,1,1,1,1,0},
                        {0,1,1,1,1,1,1,1,1,0},
                        {0,0,0,0,0,0,0,0,0,0} }; 
   
   printf("Введите начальную точку:\n");
   scanf("%d %d", &x, &y);
   
   printf("Конечную:\n");
   scanf("%d %d", &exitX, &exitY);
   
   ExitLabirint(x, y);
   
   if (flag == 1)
      printf ("Yes\n");
   else
      printf ("No\n");
	
   return 0;	
}

[Ламер_001]

пара советов:
функцию LegalStep можно убрать расширив размеры лабиринта сверху снизу и с боков заполнив их как недоступные. и второе когда рекурсивно вызываете ExitLabirint помечайте текущую позицию как пройденную а при возврате сбросте значение

[karamelka87]

Проверку легальности хода убрала (спасибо).
Но остается не понятно почему оно все равно присваивает flag значение 1, ведь если выхода нету то значение выхода не будет обозначено двойкой.

[Ламер_001]

попробуйте пройтись пошагово - обычно помогает

[karamelka87]

вывела шаги, он у меня почему-то по единицам ходит.
теперь совсем запуталась, весь if проверяют на ноль, почему он туда идет все равно?

[MaTBeu]

И где у вас условие проверки ПОЛЯ на ноль? Я вижу только проверку на выход за пределы лабиринта.

[karamelka87]

Вот исправленный код:

#include <stdio.h>
#define MAX_NUMBERS 12
int labirint[MAX_NUMBERS][MAX_NUMBERS];
int exitX, exitY , flag;

int TakeNumbers()
{
   int i, j;
   
   printf ("10*10 maze\n");
   for (j=1; j<(MAX_NUMBERS-1); ++j)
   {
      for(i=1; i<(MAX_NUMBERS-1); ++i)
      {
         scanf("%d", &labirint[i][j]); 
      } 
   }    
}

int ExitLabirint(int x, int y)
{   
   if (labirint[x][y] == 1)
      return 0;
   
   if (labirint[exitX][exitY] == 2)
      {
      flag = 1;
      return 0;
      }    
      
   labirint[x][y] = 2; 
       
   if (labirint[x+1][y] == 0)
         ExitLabirint (x+1,y);
   if (labirint[x][y+1] == 0)
         ExitLabirint (x, y+1);
   if (labirint[x-1][y] == 0)
         ExitLabirint (x-1, y); 
   if (labirint[x][y-1] == 0) 
         ExitLabirint (x, y-1);    
   labirint[x][y] = 0;           
}

void FillFrame ()
{
   int i, j;
   for (i=0; i<MAX_NUMBERS; ++i)
   {
       labirint[0][i] = 1;
       labirint[MAX_NUMBERS-1][i] = 1;
   }
   for (j=0; j<MAX_NUMBERS; ++j)
   {
       labirint[j][0] = 1;
       labirint[j][MAX_NUMBERS-1] = 1;
   }
} 

int main()
{
   int x, y;
   int tempX, tempY;
   int tempExitX, tempExitY; 
   
   TakeNumbers();
   
   FillFrame();       
   
   printf("start\n");
   scanf("%d %d", &tempX, &tempY);
   
   x = tempX + 1;
   y = tempY + 1;
   
   printf("end\n");
   scanf("%d %d", &tempExitX, &tempExitY);
   
   exitX = tempExitX + 1;
   exitY = tempExitY + 1;
   
   if (labirint [x][y] == 1)
      flag = 0;
   else
      ExitLabirint(x, y);
   
   if (flag == 1)
      printf ("Yes\n");
   else
      printf ("No\n");
    	
	return 0; 	
}

if (labirint[x][y] == 0) проверяет если можно поити в одну из сторон.

[Ламер_001]

в общем объясню на словах, писать код времени нет:
как надо организовать функцию. на входе она получает 2 параметра: x; y.
первое действие проверяем флаг. если он false то проверяем явлются ли наши x и y концами (искомый выход) если да то флаг тру и выходим иначе делаем следующее, объясню для одной стороны для других аналогично
если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0;
т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее.

вот

[FlashKa]

Хочу предложить иной способ решения данной задачи.
Рекурсия это конечно хорошо, код программы получается маленький и компактный, но в данном случае я бы использовал "волновой метод".
Сложность рекурсии О(2^N), "волновой метод" O(N*N).
При большом желании могу написать код который выводит кратчайший путь или сообщение что пути нет в противном случае.

[karamelka87]

кратчайший путь не надо =) просто проверить есть ли он вообще =)
но если есть готовый код то буду рада посмотреть. Здать все равно не успела, но решение интересно узнать.