fork download 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int row[8] = {-2, -1, +1, +2, +2, +1, -1, -2};
  6. const int col[8] = {+1, +2, +2, +1, -1, -2, -2, -1};
  7.  
  8. void try2Move(int count, int x, int y, int** board, int n);
  9. void printAns(int** board, int n);
  10. bool isInBoard(int x, int y, int n);
  11.  
  12. int main() {
  13.     int n;
  14.     cin >> n;
  15.  
  16.     int** board = new int*[n]();
  17.     for(int i=0; i<n; i++)
  18.         board[i] = new int[n]();
  19.  
  20.     int x, y;
  21.     cin >> x >> y;
  22.  
  23.     board[x][y] = 1;
  24.     try2Move(2, x, y, board, n);
  25.  
  26.     for(int i=0; i<n; i++)
  27.         delete[] board[i];
  28.     delete[] board;
  29.  
  30.     return 0;
  31. }
  32.  
  33. void printAns(int** board, int n) {
  34.     for(int i=0; i<n; i++) {
  35.         for(int j=0; j<n; j++) {
  36.             cout << board[i][j] << " ";
  37.         }
  38.         cout<<"\n";
  39.     }
  40. }
  41.  
  42. bool isInBoard(int x, int y, int n) {
  43.     if(x < 0 || x >= n) return false;
  44.     if(y < 0 || y >= n) return false;
  45.     return true;
  46. }
  47.  
  48. //===============================================================
  49.  
  50. bool checkAns = false;
  51.  
  52. bool nextCellIsFirstCell(int x, int y, int** board, int n) {
  53.     for (int i=0; i<8; i++) {
  54.         int xN = x + row[i];
  55.         int yN = y + col[i];
  56.         if(!isInBoard(xN, yN, n)) continue;
  57.  
  58.         if(board[xN][yN] == 1)
  59.             return true;
  60.     }
  61.     return false;
  62. }
  63.  
  64. int numCan(pair<int, int> cur, int** board, int n) {
  65.     int x = cur.first;
  66.     int y = cur.second;
  67.     int num = 0;
  68.  
  69.     for(int i=0; i<8; i++) {
  70.         int xN = x + row[i];
  71.         int yN = y + col[i];
  72.         if(!isInBoard(xN, yN, n)) continue;
  73.  
  74.         if(board[xN][yN] > 0) continue;
  75.         num++;
  76.     }
  77.  
  78.     return num;
  79. }
  80.  
  81. void try2Move(int count, int x, int y, int** board, int n) {
  82.     if(checkAns == true) return;
  83.     if(count > n*n) {
  84.         if(!nextCellIsFirstCell(x, y, board, n)) return;
  85.         printAns(board, n);
  86.         checkAns = true;
  87.     }
  88.  
  89.     pair<int, int> candidates[8];
  90.     int nCandidate = 0;
  91.  
  92.     for (int i=0; i<8; i++) {
  93.         int xN = x + row[i];
  94.         int yN = y + col[i];
  95.         if(!isInBoard(xN, yN, n)) continue;
  96.  
  97.         //If the number of candidates of first knight's
  98.         //position is 0, it means there're no way back 
  99.         //to the first position
  100.         if(board[xN][yN] == 1) {
  101.             if(numCan({xN, yN}, board, n) == 0) return;
  102.         }
  103.  
  104.         if(board[xN][yN] == 0) {
  105.             candidates[nCandidate++] = {xN, yN};
  106.         }
  107.     }
  108.  
  109.     // Sort candidates by the number of next_candidates
  110.     // using bubble sort
  111.     for(int i=0; i < nCandidate - 1; i++) {
  112.         for (int j = 0; j < nCandidate - i - 1; j++) {
  113.             int num_a = numCan(candidates[j], board, n);
  114.             int num_b = numCan(candidates[j+1], board, n);
  115.             if(num_a > num_b)
  116.                 swap(candidates[j], candidates[j+1]);
  117.         }
  118.     }
  119.  
  120.     for(int i=0; i < nCandidate; i++) {
  121.         int xN = candidates[i].first;
  122.         int yN = candidates[i].second;
  123.         if(!isInBoard(xN, yN, n)) continue;
  124.  
  125.         if(board[xN][yN] == 0) {
  126.             board[xN][yN] = count;
  127.             try2Move(count+1, xN, yN, board, n);
  128.             board[xN][yN] = 0;
  129.         }
  130.     }
  131. }
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin 
12
0 0
stdout 
1 24 143 62 3 26 127 96 5 28 31 92 
140 61 2 25 136 97 4 27 126 93 6 29 
23 144 139 142 63 128 125 98 95 30 91 32 
60 141 64 135 124 137 100 129 102 81 94 7 
65 22 123 138 133 130 121 114 99 90 33 80 
110 59 134 119 122 115 132 101 82 103 8 85 
21 66 111 116 131 120 113 106 89 84 79 34 
58 109 118 73 112 107 88 83 104 45 86 9 
67 20 69 108 117 74 105 46 87 78 35 44 
54 57 72 75 70 51 40 77 42 47 10 13 
19 68 55 52 17 76 49 38 15 12 43 36 
56 53 18 71 50 39 16 41 48 37 14 11
https://ideone.com/aI0UDf
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!