Информатика и технология программирования


Обход шахматной доски - часть 2


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


//------------------------------------------------------bk54-02.cpp


//------Обход шахматной доски конем


int desk[8][8]; // поля доски


int nstep; // номер шага


int step(int x0, int y0)
{
static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода


if (x0 &#60 0 || x0 &#62=7 || y0 &#60 0 || y0 &#62=7 )
return(0); // выход за пределы доски


if (desk[x0][y0] !=0)
return(0); // поле уже пройдено


desk[x0][y0] = nstep++; // отметить свободное поле


if (nstep == 64)
return(1); // все поля отмечены - успех


for (i=0; i&#60 8; i++)
if (step(x0+xy[i][0], y0+xy[i][1]))
return(1); // поиск успешного хода


nstep--; // вернуться на ход назад


desk[x0][y0] = 0; // стереть отметку поля


return(0); // последовательность не найдена


}
void Path(int x0, int y0)
{
int i,j; // очистка доски


for (i=0; i&#60 8; i++)
for (j=0; j&#60 8; j++) desk[i][j] =0;
nstep = 1; // установить номер шага


step(x0,y0); // вызвать функцию для исходной


} // позиции




Начало  Назад  Вперед



Книжный магазин