LINUX.ORG.RU

Волновой алгоритм.Задача про лабиринт.

 , волновой алгоритм


0

1

Всем доброго времени суток.Нужна помощь с двумя флагами лабиринта,один из которых отвечает за факт проходимости/непроходимости, а другой - за факт того,что мы пришли к выходу.То,что должно искать свободные и существующие клетки и заполнять их уже написано,осталось только выйти либо узнать,что выхода нет.Код цикла,который за всё это отвечает


  do
   {
     numWave++;
     flag=-1; 
     
//    if  ((flagend!=1)&&(flag!=0))
     {
      for (i=0;i<n;i++)
       {

	     for (j=0;j<n;j++)
		  {  
		
		if (a[i][j]==numWave)                         
		 {
			 
		  //проверка на существование и  проходимость
			if ((j>=1)&&(a[i][j-1]==0))        
			 {
				a[i][j-1]=numWave+1;	 flag=1;
			 }
			if ((j+1<n)&&(a[i][j+1]==0))    
			 {
			       a[i][j+1]=numWave+1;  flag=1;
			 }
			if ((i>1)&&(a[i-1][j]==0))    
			 {
				 a[i-1][j]=numWave+1;    flag=1;
			 }
			if ((i+1<n)&&(a[i+1][j]==0))  
			 {
				 a[i+1][j]=numWave+1;    flag=1;
			 }
			 
		     if (a[i][j]==pend)   //если мы достигли выхода
			  {
				    flagend=1;
					break;
			  }	
		 }  				//if
	  }  					//for j


//если флаг проходимости не был достигнут
		if (flag!=1)   flag=-1;      		
		 
//   если мы достигли выхода		 
		 if (flagend==1) break;


     }     //for i
    } //if flagend!=1
    
    if (flagend==1) break;	
  }
while ((flagend!=1)||(flag!=-1));

numWave-номер волны,flag-отвечает за проходимость,flagend-отвечает за факт достижения выхода,pend==-3;-точка конца,т.е. которую нужно достичь.

При while ((flagend!=1) || (flag!=-1)); бесконечный цикл,а при while ((flagend!=1) && (flag!=-1)); заполняется ВСЯ матрица номерами волн,хотя мне нужно,чтобы он заполнял только до клетки выхода,которая находится где -то около середины лабиринта.Лабиринт один и тот же пока (10x10) если нужно ,могу написать его.

мне нужно,чтобы он заполнял только до клетки выхода

Используй goto вместо break.

Хотя мне просто не нравится этот стиль, даже в рамках стиля код ужасен. Часть отступов потеряна, часть пробелами, часть табами. Какие-то мусорные комментарии. Не понятно, что значит flag.

И ещё. Чем этот алгоритм отличается от алгоритма Дейкстры?

i-rinat ★★★★★
()
Последнее исправление: i-rinat (всего исправлений: 1)

перебирать каждый раз все поле не хорошо. лучше уж хранилище координат i-той волны.

по делу:

//если флаг проходимости не был достигнут
		if (flag!=1)   flag=-1;      		
		 
//   если мы достигли выхода		 
		 if (flagend==1) break;


     }     //for i
    } //if flagend!=1
    
    if (flagend==1) break;	
  }
while ((flagend!=1)||(flag!=-1));
заменить на:
//   если мы достигли выхода		 
       if (flagend==1) break;
     }     //for i
    } //if flagend!=1
    
//если флаг проходимости не был достигнут
    if (flag==-1) break;
  }
while (flagend!=1);

anonymous
()
Ответ на: комментарий от anonymous

ещё вот тут кажется ошибка:

if (a[i][j]==pend)   //если мы достигли выхода
заменить на:
if (&a[i][j]==pend)   //если мы достигли выхода
и объявление не забудь исправить: int* pend;

anonymous
()
Ответ на: комментарий от i-rinat

Чем этот алгоритм отличается от алгоритма Дейкстры?

Например тем, что в невзвешенном графе алгоритм Дейкстры имеет худшую асимптотику и потому не нужен.

metar ★★★
()
Последнее исправление: metar (всего исправлений: 1)
Ответ на: комментарий от i-rinat

Ну это ведь пока заготовка,черновик.Переделывать буду,когда буду знать,что всё работает.

Какие-то мусорные комментарии.

Если ты про «//if»,«//for i».. - как видно,код большой и мне удобно знать,что означает та или иная скобка.А если про «//if flagend!=1» - это была просто одна из идей для решения,но сейчас я её полностью убрал.

Не понятно, что значит flag.

Повторюсь,эта переменная отвечает за факт проходимости/непроходимости.

Hoffman
() автор топика
Ответ на: комментарий от anonymous

заменить на:

[cut]
//   если мы достигли выхода		 
       if (flagend==1) break;
     }     //for i
    } //if flagend!=1
    
//если флаг проходимости не был достигнут
    if (flag==-1) break;
  }
while (flagend!=1);
[/cut]

Заменил.Не работает.Тогда я попробовал идею с указателем.Опять не работает.Убрал.И исправил вот что:

//если мы достигли выхода
if (a[i][j]==pend) 	   
{
  flagend=1;
  break;
 }	


на

//если мы достигли выхода 
if ((a[i-1][j]==pend)||(a[i+1][j]==pend)||(a[i][j-1]==pend)||(a[i][j+1]==pend))   	

И вроде заработало-дальше клетки выхода матрица не заполняется.Всем спасибо.

Hoffman
() автор топика
Ответ на: комментарий от Hoffman

Если ты про «//if»,«//for i»..

Это я просто злой был. Вообще, имел в виду вот это:

//    if  ((flagend!=1)&&(flag!=0))

Что касается других комментариев, они не очень-то и нужны. Сейчас ты экономишь на пробелах, но впустую расходуешь вертикальное пространство. Если поменять стиль и выдержать отступы, код станет компактнее, и необходимость в пояснениях отпадёт. Вот твой код:

do {
    numWave ++;
    flag = -1;

    for (i = 0; i < n; i ++) {
        for (j = 0; j < n; j ++) {
            if (a[i][j] == numWave) {
                //проверка на существование и  проходимость
                if (j >= 1 && a[i][j-1] == 0) {
                    a[i][j-1] = numWave + 1;
                    flag = 1;
                }
                if (j + 1 < n && a[i][j+1] == 0) {
                    a[i][j+1] = numWave + 1;
                    flag = 1;
                }
                if (i > 1 && a[i-1][j] == 0) {
                    a[i-1][j] = numWave + 1;
                    flag = 1;
                }
                if (i + 1 < n && a[i+1][j] == 0) {
                    a[i+1][j] = numWave+1;
                    flag = 1;
                }
                if (a[i][j] == pend) {   //если мы достигли выхода
                    flagend = 1;
                    break;
                }
            } //if
        } // for j
        
        //если флаг проходимости не был достигнут
        if (flag != 1)
            flag = -1;

        // если мы достигли выхода
        if (flagend == 1)
            break;
    } //for i

    if (flagend == 1)
        break;
} while (flagend != 1 || flag != -1);

Это придирки по стилю. Теперь по мелочам в коде:

        //если флаг проходимости не был достигнут
        if (flag != 1)
            flag = -1;
Во-первых, традиционно для флагов используют 0 и 1, а не -1 и 1. 0 и 1 позволяют использовать флаг как boolean переменную, то есть писать if (flag) и if (!flag) вместо if (flag == 1) и if (flag == 0). Можно даже давать осмысленные имена флагам, вроде exit_found: «if (exit_found)» выглядит понятнее, чем if (flag == 1).

Во-вторых, flag у тебя принимает значения только -1 и 1. А значит, если flag != 1, то flag уже установлен в -1. И этот if абсолютно бесполезен.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

И этот if абсолютно бесполезен.

Точно,спасибо.

0 и 1 - это уже стенки :).
Если я не ошибаюсь, объявлять boolean переменные в си bool flag,exit_found -вот так?

Hoffman
() автор топика
Ответ на: комментарий от Hoffman

объявлять boolean переменные в си

В Си нет булевых переменных. Вместо них — любые другие. 0 — ложь, всё остальное — истина.

i-rinat ★★★★★
()
Ответ на: комментарий от Hoffman

объявляют так (именно в коде на Си)

bool есть в C++. В C — нет. Но никто не запрещает сделать typedef int bool, если так хочется.

i-rinat ★★★★★
()
Ответ на: комментарий от TakeOver

емнип, в си есть _Bool

Надо же, gcc и правда проглатывает.

i-rinat ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.