VPF::Ход конем алгоритм - Форум программистов

odys

Дата 3.12.2008, 15:48 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 28
Регистрация: 9.11.2008

Репутация: нет
Всего: нет

В общем есть программа под названием ход конем.
Ее задача, это двигать коня по полю, таким образом, что бы он обошел площадку. При координатах 2 1 Программа успешно выполняет задачу, однако при симетричном значении 1 2 - нет.

алгоритм. В массиве numbers для каждой клетки хранится количество доступных отходов с этой клетки. (для угловых 2, центральных 8) и при прочих равных, конь ходит на площадку с меньшим таким номером

Вот собственно программа

Код


#include <iostream>
#include <iomanip>
using namespace std;
const int size = 8;
int numbers [size][size];      // Для каждого поля показывает сколько вариантов отхода с него на другие поля доски
bool trace [size][size] = {0}; // Хранит координаты полей, на которых побывал конь.
int shagNum [size] [size];     // Показывает на каком по порядку шаге, конь вступил на это поле.
int z = 1;

void print_numbers( void );
void print_shugNum( void );
void print_shag (void);
int hod_konem (int &, int &); //Выдает минимальное значение поля, на которое можно перейти
int make_shag (int x, int y);
void full_numbers (void);

int perehod[8][2] = { {1,2}, {1,-2}, {2,1}, {2,-1}, {-1,2}, {-1,-2}, {-2,1}, {-2,-1}};

int main()
{
 int x, y;
 std::cout<<" Input x and y ";
 cin>>x>>y;
 full_numbers();
    while (make_shag (x, y) != 0)

    {

      hod_konem (x, y);



    }
    shagNum[x][y] = z;
    std::cout<<"           HOD KONEM          "<<endl;
    print_shugNum();
    std::cout<<"-------------------------------"<<endl;
    std::cout<<" Last value = "<<z<<" x = "<<x<< " y = "<<y<<endl;
    std::cout<<"-------------------------------"<<endl;

 std::cin.get();
 std::cin.get();

 return 0;
}

//--------------------------------------------------------------------------------

int make_shag (int x, int y)
{
 int j = 0;
 if ( (trace[x + 2][y - 1] != 1) && ( x + 2 < size ) && ( y - 1 >=   0)) {j++;}
 if ( (trace[x + 2][y + 1] != 1) && ( x + 2 < size ) && ( y + 1 < size)) {j++;}
 if ( (trace[x + 1][y - 2] != 1) && ( x + 1 < size ) && ( y - 2 >=   0)) {j++;}
 if ( (trace[x + 1][y + 2] != 1) && ( x + 1 < size ) && ( y + 2 < size)) {j++;}
 if ( (trace[x - 1][y - 2] != 1) && ( x - 1 >=   0 ) && ( y - 2 >=   0)) {j++;}
 if ( (trace[x - 1][y + 2] != 1) && ( x - 1 >=   0 ) && ( y + 2 < size)) {j++;}
 if ( (trace[x - 2][y - 1] != 1) && ( x - 2 >=   0 ) && ( y - 1 >=   0)) {j++;}
 if ( (trace[x - 2][y + 1] != 1) && ( x - 2 >=   0 ) && ( y + 1 < size)) {j++;}
 return j;
}
//--------------------------------------------------------------------------------
void full_numbers (void)
{
 for (int i = 0; i < size; i++)
 {   for (int j = 0; j < size; j++)
     {
        numbers[i][j] =  make_shag ( i, j);
     }
 }
}
//--------------------------------------------------------------------------------

void print_numbers(void)
{
   for (int i = 0; i < size; i++)
 {   for (int j = 0; j < size; j++)
     {
        std::cout<<setw(3)<<numbers[i][j]<<" ";
     }
     std::cout<<endl;
 }

}
//--------------------------------------------------------------------------------
void print_shugNum(void)
{
   for (int i = 0; i < size; i++)
 {   for (int j = 0; j < size; j++)
     {
        std::cout<<setw(3)<<shagNum[j][i]<<" ";
     }
     std::cout<<endl;
 }

}

//--------------------------------------------------------------------------------

int hod_konem (int &x, int &y)
{
 trace[x][y] = 1;
 shagNum [x] [y] = z;
 int min = 10;
 int x0, y0;
 int r, t;
 for (int i = 0; i < 8; i++)
    {

     r = perehod[i][0];
     t = perehod[i][1];
     if ( (trace[x + r][y + t] != 1) && (x + r < size ) && (x + r >= 0 ) && ( y + t < size) &&( y + t >= 0) && (numbers[x + r][y + t] <= min ) )
        {
          if (numbers[x + r][y + t] < min ) {
             min = numbers[x + r][y + t];
             x0 = x + r;
             y0 = y + t;                    }
        /*  if (numbers[x + r][y + t] == min ) {
          if ( hod_konem (x + r, y + t) < hod_konem (x0, y0) )
             {
             x0 = x + r;
             y0 = y + t;
             }
                                            }*/
        }

    }
  x = x0;
  y = y0;
 z++;
 return min;
}

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

aram90

Дата 3.12.2008, 22:31 (ссылка)

(нет голосов)

Загрузка ...

Bug hunter

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 1.12.2008
Где: Yerevan, Armenia

Репутация: нет
Всего: 3

Надо делать перебор, только с перва посмотреть поля, с которых количество отходов минимальна.
Если несколько таковых, рассмотриваем все по очереди ( а по какой, не имеет значение).

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »