C++ Домик...

[Alina_Honey]

Прошу очень о помощи. Вот по программированию задали задачку:
Нарисовать домик, не отрывая карандаша от листа бумаги и не проводя одну и ту же линию дважды.
Требуется найти все возможные варианты рисования домика, начиная с левого нижнего угла. Нумерация вершин дома приведена на рисунке.
Например, следующая последовательность должна быть выдана на экран 153125432.(Рисунок ниже)

Среда Microsoft Visual C++ 6.0.

[Alina_Honey]

Сначала, я задаю матрицу смежности:
01101
10101
11011
00101
11110

int a[4][4]=0,1,...,1,1,0;
int j,k,l,i;

Далее с помощью циклов создаю первый проход:

{for (k=1;k<4; k++)
for(i=0;i<4; i++)
for(j=0;j<4; j++)
{if a[i;j]==1 
{l++;
if l==k
{printf(a[i;j]/n);
a[i;j]=0;
a[j,i]=0;}
}
}

но проблема в том, что после того, как происходит переход например из 1-й вершины во 2-ю, как сделать так, что бы оно не продолжало идти по матрице дальше, а перешло к вершине которую выбрало...?
Помогите...

[Alina_Honey]

Ну неужели никто не может помочь?...

[Son Of Pain]

Видимо, никто не может понять сути вопроса.

[Alina_Honey]

Я задала, что бы по циклу программа начиная с первой вершины по матрице смежности смотрела дальше, соединена ли она с другими, если да, то единички убираются(поскольку мы проходим это ребро) но вместо того, что бы перейти к той вершине, которую программа выбрала, она продолжает идти дальше( поскольку идет цикл). Мне нужна помощь в том, что бы она переходила к вершине, которую выбрала.
Например:
Изначально в программе первая вершина выбрана. Далее по матрице смежности выбирается ребро по которому идем дальше. Например ребро, соединяющее 1-ю и -ю вершины. И по логике дальше нужно выбирать ребро для второй вершины, но программа продолжает идти по этой же вершине... Вот в чем проблема...

[WebbMan]

Может поможет:
153125432 = 9 цифр, то есть если цифр>9 или цифр<9 то не подходит. то есть обязательно нужно совершить девять шагов.
Можно где то в цикле проверять на прохождение уже пройденного пути таким способом:
153125432 нет совпадений в переходах значит подходит.
15315 совпадение значит не подходит, пропускаем этот вариант.
Сейчас сама попробую сделать если получиться отпишу.

[WebbMan]

А вот так нельзя? поверька...
сумма верного хода чисел равна 26
153125432 = 26
253215431 = 26
153125432 = 26
делаем циклами любые варианты и проверяем нет ли совпадений типо 15315

[WebbMan]

и еще проверяем строку str = strlen(153125432) на длинну... str = 9

[Ezhuk]

Тут рационально делать рекурсией.

void fun(int ms[5][5], int pos, int step, int sq[9]) 
{ 

   for(int i=0;i<5;i++)
      int flag=0; 
      if(ms[pos][i]){
           pos=ms[pos][i]; // если возможно идти дальше в pos заносим новую позицию.
           sq[step]=pos;
           if(step>1){
           for(int k=0;k<step-1;k++){ // проверка на прохождение ребер второй раз
                if((sq[i]== pos && sq[i+1]==sq[step]) || (sq[i+1]== pos && sq[i]==sq[step])) {flag=1; break;}
           }
           if (step==8 && flag==0){ 
               for(int i=0;i<9;i++)
                    printf("%d",sq[i]+1);// +1 что обозначения были от 1 до 5
     
               if(flag==0 && step<8) fun(ms,pos,step++,sq); // если флаг 0 то идем дальше
           
      }
}
   
int main(){
    int ms[5][5],pos,step,sq[9]=0;
    ...
    вводим матрицу смежности
    ...
    for(int i=0;i<5;i++){ // определяем исходную точку
         sq[0]=i;
         fun(ms,i,1,sq);}
}

Щас проверить возможности нет. Надеюсь ошибок нет. Как будет возможность проверю.
Можно еще оптимизировтаь убрать переменную pos и работать только с sq, но это переделывать лень 8)

[Alina_Honey]

Хм... спасибо, попробую)