fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int board[8][8];
  5. vector<int> ds[64];
  6. int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
  7. int dy[] = {1, -1, 2, -2, 2, -2, -1, 1};
  8. const int N = 64;
  9. int path[N];
  10. bool vis[N];
  11. int x, y, s;
  12. vector<pair<int, int>> qu(64);
  13. int res[8][8];
  14.  
  15. void xay() {
  16.     int cnt = 0;
  17.     for (int i = 0; i < 8; i++) {
  18.         for (int j = 0; j < 8; j++) {
  19.             qu[cnt] = {i, j};
  20.             cnt++;
  21.         }
  22.     }
  23. }
  24.  
  25. bool check(int x, int y) {
  26.     return (x >= 0 && x < 8 && y >= 0 && y < 8);
  27. }
  28.  
  29. void convert() {
  30.     int cnt = 0;
  31.     for (int i = 0; i < 8; i++) {
  32.         for (int j = 0; j < 8; j++) {
  33.             board[i][j] = cnt++;
  34.         }
  35.     }
  36.     for (int i = 0; i < 8; i++) {
  37.         for (int j = 0; j < 8; j++) {
  38.             for (int k = 0; k < 8; k++) {
  39.                 int nx = i + dx[k], ny = j + dy[k];
  40.                 if (check(nx, ny)) {
  41.                     ds[board[i][j]].push_back(board[nx][ny]);
  42.                 }
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. bool issafe(int v, int pos) {
  49.     if (find(ds[path[pos - 1]].begin(), ds[path[pos - 1]].end(), v) == ds[path[pos - 1]].end()) {
  50.         return false;
  51.     }
  52.     return !vis[v];
  53. }
  54.  
  55. bool hal(int pos) {
  56.     if (pos == 64) return true;
  57.     sort(ds[path[pos - 1]].begin(), ds[path[pos - 1]].end(), [](int a, int b) {
  58.         return ds[a].size() < ds[b].size();
  59.     });
  60.  
  61.     for (int v : ds[path[pos - 1]]) {
  62.         if (issafe(v, pos)) {
  63.             path[pos] = v;
  64.             vis[v] = true;
  65.             if (hal(pos + 1)) return true;
  66.             path[pos] = -1;
  67.             vis[v] = false;
  68.         }
  69.     }
  70.     return false;
  71. }
  72.  
  73. void doi() {
  74.     int cnt = 1;
  75.     for (int i = 0; i < 64; i++) {
  76.         int temp = path[i];
  77.         int z = qu[temp].first, t = qu[temp].second;
  78.         res[z][t] = cnt++;
  79.     }
  80.     for (int i = 0; i < 8; i++) {
  81.         for (int j = 0; j < 8; j++) {
  82.             cout << res[i][j] << ' ';
  83.         }
  84.         cout << endl;
  85.     }
  86. }
  87.  
  88. void tim() {
  89.     memset(path, -1, sizeof(path));
  90.     memset(vis, false, sizeof(vis));
  91.     path[0] = s;
  92.     vis[s] = true;
  93.     if (hal(1)) {
  94.         doi();
  95.     }
  96. }
  97.  
  98. int main() {
  99.     ios_base::sync_with_stdio(false);
  100.     cin.tie(nullptr);
  101.     //freopen("output.txt", "w", stdout);
  102.     convert();
  103.     xay();  
  104.     cin >> x >> y;
  105.     s = board[y - 1][x - 1];  
  106.     tim();
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
2 1
stdout
copy 
4 1 6 21 32 39 16 19 
7 22 3 38 17 20 31 40 
2 5 48 33 62 55 18 15 
23 8 37 60 49 30 41 54 
36 47 34 63 56 61 14 29 
9 24 57 50 59 64 53 42 
46 35 26 11 44 51 28 13 
25 10 45 58 27 12 43 52
https://ideone.com/sSdEH3
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

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!