Обход шахматной доски ходом коня
Конь должен побывать в каждой клетке доски размером ровно один раз. Примем нумерацию возможных ходов коня из клетки как это изображено на рисунке. В стеке будем хранить координаты покидаемой клетки и номер выполняемого хода. Когда обнаружится, что никакой ход из клетки невозможен, берем координаты предыдущей клетки из стека и пытаемся покинуть ее с помощью хода, имеющего номер на единицу больше, чем тот ход, с помощью которого ее покидали ранее (операция "возврат"). Если уже посетили все клеток, то задача решена, и трасса обхода лежит в стеке. Если при попытке взять клетку из стека, обнаруживается, что стек пуст, то это означает, что задача не имеет решения. Ниже приведен текст программы.
struct STACK{
int i,j; // координаты клетки
int move; // номер хода, которым покидаем клетку
}; // элемент стека
bool Horse(int n, STACK *stack);
//-----------------------------------
static bool Move(int N, int i1,int j1, int n, int *i2, int *j2){
// Ход коня. Конь ходит из клетки i1,j1 ходом номер n
// и попадает в клетку *i2,*j2
// N - размер доски
// Возвращает true при успехе
switch(n){
case 0:
*i2=i1+1;
*j2=j1+2;
Break;
case 1:
*i2=i1+2;
*j2=j1+1;
Break;
case 2:
*i2=i1+2;
*j2=j1-1;
Break;
case 3:
*i2=i1+1;
*j2=j1-2;
Break;
case 4:
*i2=i1-1;
*j2=j1-2;
Break;
case 5:
*i2=i1-2;
*j2=j1-1;
Break;
case 6:
*i2=i1-2;
*j2=j1+1;
Break;
case 7:
*i2=i1-1;
*j2=j1+2;
Break;
default:
// сюда можно попасть только при ошибке в программе
*i2=INT_MAX;
*j2=INT_MAX;
}
return (*i2>=0 && *i2<N && *j2>=0 && *j2<N);
}
//-----------------------------------
bool Horse(int n, STACK *stack){
// n - размер доски.
// результат будет получен в стеке stack.
// Каждый раз, когда покидаем клетку, ее координаты
// и номер хода помещаем в стек.
// возврат true - успех
bool **Board=NULL; // в массиве доска n*n помечаем факт посещения клетки
int i,j; // текущие координаты клетки
int v; // указатель стека
Дата добавления: 2014-12-02; просмотров: 921;