#include<iostream>
#include<iomanip>
#include<conio.h>
#include<stdio.h>
using std::endl;
using std::setw;
/* Knight Tour */
const int maxx = 100;
int size;
int K[maxx][maxx], access[maxx][maxx];
int SUB_ROW[8], SUB_COL[8];
int ver[] = {+2, -1, -1, -2, -2, +1, +1, +2};
int hor[] = {-1, +2, -2, -1, +1, -2, +2, +1};
int row, col,times;
bool CHECK ( int row, int col )
{
if ( row > size-1 || row < 0 || col > size-1 || col < 0 || K[row][col] != 0 )
return false;
else
return true;
}
void PRINT()
{
for ( int i = 0; i < size; i++ )
{
for ( int j = 0; j < size; j++ )
cout << setw
(3) << K
[i
][j
] ; }
cout << "----------------------------" << endl
; getch();
}
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void HEURISTIC( int row, int col, int &step, int ORDER[8] )
{
int poss_row, poss_col; /* Gia su nhung kha nang cua ROW va COL */
/* BAT DAU SINH BANG ACCESSIBILITY */
for ( int i = 0; i < size; i++)
{
for ( int j = 0; j < size; j++)
{
access[i][j] = 0;
for (int k = 0; k < size; k++)
{
poss_row = i + ver[k];
poss_col = j + hor[k];
if ( CHECK(poss_row, poss_col) )
access[i][j]++;
}
}
}
/* KET THUC SINH BANG */
int ROW_I, ROW_II;
int COL_I, COL_II;
/* BAT DAU KHOI TAO GIA TRI CHO SUB_ROW[] va SUB_COL[] */
step = 0; /* THE MOST IMPORTANT */
for ( int i = 0; i < 8; i++)
{
poss_row = row + ver[i];
poss_col = col + hor[i];
if ( CHECK(poss_row, poss_col) )
{
SUB_ROW[step] = poss_row;
SUB_COL[step] = poss_col;
ORDER[step] = step; /* Luu lai trang thai cua Row va Col */
step++;
}
}
/* KET THUC */
/* SO SANH CHON RA BUOC NHAY TOI UU NHAT */
for ( int i = 0; i < step ; i++)
{
for ( int j = i + 1; j < step; j++)
{
ROW_I = SUB_ROW[ORDER[i]];
COL_I = SUB_COL[ORDER[i]];
ROW_II = SUB_ROW[ORDER[j]];
COL_II = SUB_COL[ORDER[j]];
if (access[ROW_I][COL_I] > access[ROW_II][COL_II])
swap(ORDER[i], ORDER[j]);
}
}
/*---------------------------------------------------*/
}
void Knight (int times, int row, int col)
{
int ORDER[8];
int moves = 0;
int next_row, next_col;
K[row][col] = times + 1;
while ( times != size*size )
{
PRINT();
HEURISTIC(row, col, moves, ORDER);
for ( int i = 0; i < moves; i++)
{
next_col = SUB_COL[ORDER[i]];
next_row = SUB_ROW[ORDER[i]];
if (CHECK(next_row, next_col ))
Knight ( times + 1, next_row, next_col);
}
}
}
int main()
{
cout << " Enter the size of board: "; cin >> size; cout << " Enter [row,col] "; cin >> row
>> col
;
Knight (0, row, col);
system("pause");
return 0;
}
Các giải thuật cho mã đi tuần?
Trả lời cùng với trích dẫn
