Re: Обход доски шахматным конем

From

Andrew Ezhguroff ()

To

Roman Zhelnov

Date

2002-07-22T23:36:56Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Roman Zhelnov" <Roman.Zhelnov@p29.f25.n5053.z2.fidonet.org>
сообщил(а):

 RZ>   Интересует алгоритм обхода доски шахматным конем. На одну клетку
 RZ> можно вставать только один раз...

Если в лоб и рекурсивно, то, например, так:

#include <stdio.h>

#define Len 8

char Tab[Len][Len];
char Res[Len*Len][3];

int Gen(int X, int Y, int Num){
  if(X<0||X>=Len||Y<0||Y>=Len||Tab[X][Y])return 0;
  Tab[X][Y]=1;
  if((++Num==Len*Len)||
     Gen(X-1, Y-2, Num)||Gen(X-1, Y+2, Num)||
     Gen(X+1, Y-2, Num)||Gen(X+1, Y+2, Num)||
     Gen(X-2, Y-1, Num)||Gen(X-2, Y+1, Num)||
     Gen(X+2, Y-1, Num)||Gen(X+2, Y+1, Num)){
    Res[--Num][0]=X+'A';
    Res[  Num][1]=Y+'1';
    return 1;
  }
  Tab[X][Y]=0;
  return 0;
}

int main(void){
  if(Gen(0, 0, 0)){
    for(int i=0; i<Len*Len; i++)printf("%3s", Res[i]);
  }else{
    printf("Ответа нет");
  }
}

С уважением, Андрей.



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)