Advertisement
Guest User

Untitled

a guest
Nov 1st, 2015
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifndef _LIBS_NAMESPACES
  2.  
  3. #include <stdlib.h>
  4. #include <iostream>
  5. #include <iomanip>
  6.  
  7. using namespace std;
  8.  
  9. #endif // _LIBS_NAMESPACES
  10.  
  11. #ifndef _LOCAL_CONSTANTS
  12.  
  13. #define PAD_LENGTH 4
  14. #define START_ROW 0
  15. #define START_COL 0
  16.  
  17. #define TOP_LEFT(row, col) row - 2, col - 1
  18. #define TOP_RIGHT(row, col) row - 2, col + 1
  19. #define BOT_LEFT(row, col) row + 2, col - 1
  20. #define BOT_RIGHT(row, col) row + 2, col + 1
  21. #define LEFT_TOP(row, col) row - 1, col - 2
  22. #define LEFT_BOT(row, col) row + 1, col - 2
  23. #define RIGHT_TOP(row, col) row - 1, col + 2
  24. #define RIGHT_BOT(row, col) row + 1, col + 2
  25.  
  26. #endif // _LOCAL_CONSTANTS
  27.  
  28. #ifndef _STRUCTS_ENUMS
  29.  
  30. typedef enum
  31. {
  32.     eTopLeft,
  33.     eTopRight,
  34.     eBotLeft,
  35.     eBotRight,
  36.     eRightTop,
  37.     eRightBot,
  38.     eLeftTop,
  39.     eLeftBot,
  40.     eInvalidMove
  41. } Move;
  42.  
  43. #endif // _STRUCTS_ENUMS
  44.  
  45. #ifndef _FUNCTION_PROTOTYPES
  46.  
  47. void CalculateKnightsTour(int startRow, int startCol);
  48. bool ProcessMove(Move nextMove, int * row, int * col);
  49. Move FindOptimalMoveChoice(int row, int col);
  50. int CalculatePossibleMoves(int row, int col);
  51. bool IsPossibleMove(int row, int col);
  52. bool IsFreeCell(int row, int col);
  53. void ProcessInput();
  54. void PrintBoard();
  55. void InitializeResources();
  56. void DisposeResources();
  57.  
  58. #endif // _FUNCTION_PROTOTYPES
  59.  
  60. #ifndef _LOCAL_DATA
  61.  
  62. static int ** board;
  63.  
  64. static int boardSize;
  65. static int currentStep = 1;
  66.  
  67. #endif // _LOCAL_DATA
  68.  
  69. #ifndef _MAIN
  70.  
  71. int main()
  72. {
  73.     ProcessInput();
  74.     InitializeResources();
  75.     CalculateKnightsTour(START_ROW, START_COL);
  76.     PrintBoard();
  77.  
  78.     DisposeResources();
  79.  
  80.     return 0;
  81. }
  82.  
  83. #endif // _MAIN
  84.  
  85. #ifndef _ALGO_IMPLEMENTATION
  86.  
  87. void CalculateKnightsTour(int startRow, int startCol)
  88. {
  89.     int currentRow = startRow;
  90.     int currentCol = startCol;
  91.  
  92.     bool resultFound;
  93.  
  94.     do
  95.     {
  96.         resultFound = false;
  97.         Move nextMove = FindOptimalMoveChoice(currentRow, currentCol);
  98.         resultFound = ProcessMove(nextMove, &currentRow, &currentCol);
  99.  
  100.     } while(resultFound);
  101. }
  102.  
  103. bool ProcessMove(Move nextMove, int * row, int * col)
  104. {
  105.     switch (nextMove)
  106.     {
  107.         case eTopLeft:
  108.             (*row) -= 2;
  109.             (*col) -= 1;
  110.             break;
  111.         case eTopRight:
  112.             (*row) -= 2;
  113.             (*col) += 1;
  114.             break;
  115.         case eBotLeft:
  116.             (*row) += 2;
  117.             (*col) -= 1;
  118.             break;
  119.         case eBotRight:
  120.             (*row) += 2;
  121.             (*col) += 1;
  122.             break;
  123.         case eLeftTop:
  124.             (*row) -= 1;
  125.             (*col) -= 2;
  126.             break;
  127.         case eLeftBot:
  128.             (*row) += 1;
  129.             (*col) -= 2;
  130.             break;
  131.         case eRightTop:
  132.             (*row) -= 1;
  133.             (*col) += 2;
  134.             break;
  135.         case eRightBot:
  136.             (*row) += 1;
  137.             (*col) += 2;
  138.             break;
  139.         default:
  140.             return false;
  141.     }
  142.  
  143.     board[(*row)][(*col)] = ++currentStep;
  144.     return true;
  145. }
  146.  
  147. // Implementing the Warnsdorf's rule
  148. Move FindOptimalMoveChoice(int row, int col)
  149. {
  150.     int minMoves = INT_MAX;
  151.     int previousMoves = INT_MAX;
  152.     Move nextMove = eInvalidMove;
  153.  
  154.     // Top right
  155.     minMoves = min(minMoves, CalculatePossibleMoves(TOP_RIGHT(row, col)));
  156.     nextMove = minMoves != previousMoves ? eTopRight : nextMove;
  157.     previousMoves = minMoves;
  158.  
  159.     // Right top
  160.     minMoves = min(minMoves, CalculatePossibleMoves(RIGHT_TOP(row, col)));
  161.     nextMove = minMoves != previousMoves ? eRightTop : nextMove;
  162.     previousMoves = minMoves;
  163.  
  164.     // Right bot
  165.     minMoves = min(minMoves, CalculatePossibleMoves(RIGHT_BOT(row, col)));
  166.     nextMove = minMoves != previousMoves ? eRightBot : nextMove;
  167.     previousMoves = minMoves;
  168.  
  169.     // Bot right
  170.     minMoves = min(minMoves, CalculatePossibleMoves(BOT_RIGHT(row, col)));
  171.     nextMove = minMoves != previousMoves ? eBotRight : nextMove;
  172.     previousMoves = minMoves;
  173.  
  174.     // Bot left
  175.     minMoves = min(minMoves, CalculatePossibleMoves(BOT_LEFT(row, col)));
  176.     nextMove = minMoves != previousMoves ? eBotLeft : nextMove;
  177.     previousMoves = minMoves;
  178.  
  179.     // Left bot
  180.     minMoves = min(minMoves, CalculatePossibleMoves(LEFT_BOT(row, col)));
  181.     nextMove = minMoves != previousMoves ? eLeftBot : nextMove;
  182.     previousMoves = minMoves;
  183.  
  184.     // Left top
  185.     minMoves = min(minMoves, CalculatePossibleMoves(LEFT_TOP(row, col)));
  186.     nextMove = minMoves != previousMoves ? eLeftTop : nextMove;
  187.     previousMoves = minMoves;
  188.  
  189.     // Top left
  190.     minMoves = min(minMoves, CalculatePossibleMoves(TOP_LEFT(row, col)));
  191.     nextMove = minMoves != previousMoves ? eTopLeft : nextMove;
  192.     previousMoves = minMoves;
  193.  
  194.     return nextMove;
  195. }
  196.  
  197. int CalculatePossibleMoves(int row, int col)
  198. {
  199.     if (!IsPossibleMove(row, col) || !IsFreeCell(row, col))
  200.     {
  201.         return INT_MAX;
  202.     }
  203.  
  204.     int cnt = 0;
  205.  
  206.     if (IsPossibleMove(TOP_RIGHT(row, col)) && IsFreeCell(TOP_RIGHT(row, col)))
  207.     {
  208.         ++cnt;
  209.     }
  210.  
  211.     if (IsPossibleMove(TOP_LEFT(row, col)) && IsFreeCell(TOP_LEFT(row, col)))
  212.     {
  213.         ++cnt;
  214.     }
  215.  
  216.     if (IsPossibleMove(BOT_RIGHT(row, col)) && IsFreeCell(BOT_RIGHT(row, col)))
  217.     {
  218.         ++cnt;
  219.     }
  220.  
  221.     if (IsPossibleMove(BOT_LEFT(row, col)) && IsFreeCell(BOT_LEFT(row, col)))
  222.     {
  223.         ++cnt;
  224.     }
  225.  
  226.     if (IsPossibleMove(RIGHT_TOP(row, col)) && IsFreeCell(RIGHT_TOP(row, col)))
  227.     {
  228.         ++cnt;
  229.     }
  230.  
  231.     if (IsPossibleMove(RIGHT_BOT(row, col)) && IsFreeCell(RIGHT_BOT(row, col)))
  232.     {
  233.         ++cnt;
  234.     }
  235.  
  236.     if (IsPossibleMove(LEFT_TOP(row, col)) && IsFreeCell(LEFT_TOP(row, col)))
  237.     {
  238.         ++cnt;
  239.     }
  240.  
  241.     if (IsPossibleMove(LEFT_BOT(row, col)) && IsFreeCell(LEFT_BOT(row, col)))
  242.     {
  243.         ++cnt;
  244.     }
  245.  
  246.     return cnt;
  247. }
  248.  
  249. bool IsFreeCell(int row, int col)
  250. {
  251.     return board[row][col] == 0;
  252. }
  253.  
  254. bool IsPossibleMove(int row, int col)
  255. {
  256.     return row >= 0 &&
  257.            row < boardSize &&
  258.            col >= 0 &&
  259.            col < boardSize;
  260. }
  261.  
  262. #endif // _ALGO_IMPLEMENTATION
  263.  
  264. #ifndef _IO_PROCESSING
  265.  
  266. void ProcessInput()
  267. {
  268.     cin >> boardSize;
  269. }
  270.  
  271. void PrintBoard()
  272. {
  273.     for (int row = 0; row < boardSize; ++row)
  274.     {
  275.         for (int col = 0; col < boardSize; ++col)
  276.         {
  277.             cout << setfill(' ') << setw(PAD_LENGTH) << board[row][col];
  278.         }
  279.  
  280.         cout << endl;
  281.     }
  282. }
  283.  
  284. #endif // _IO_PROCESSING
  285.  
  286. #ifndef _RESOURCES_MANAGEMENT
  287.  
  288. void InitializeResources()
  289. {
  290.     board = (int**)malloc(sizeof(int*) * boardSize);
  291.  
  292.     for (int row = 0; row < boardSize; ++row)
  293.     {
  294.         board[row] = (int*)malloc(sizeof(int) * boardSize);
  295.  
  296.         for (int col = 0; col < boardSize; ++col)
  297.         {
  298.             board[row][col] = 0;
  299.         }
  300.     }
  301.  
  302.     board[0][0] = 1;
  303. }
  304.  
  305. void DisposeResources()
  306. {
  307.     for (int row = 0; row < boardSize; ++row)
  308.     {
  309.         free(board[row]);
  310.     }
  311.  
  312.     free(board);
  313. }
  314.  
  315. #endif // _RESOURCES_MANAGEMENT
Advertisement
RAW Paste Data Copied
Advertisement