fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define n 8
  3. using namespace std;
  4.  
  5. static int x_move[n] = {2, 2, -1, -1, 1, 1, -2, -2};
  6. static int y_move[n] = {1, -1, 2, -2, 2, -2, 1, -1};
  7.  
  8. void print(int arr[][n]) {
  9. 	for (int i = 0 ; i < n ; ++i) {
  10. 		for (int j = 0 ; j < n ; ++j)
  11. 			cout<<arr[i][j]<<" ";
  12. 		cout<<"\n";
  13. 	}
  14. }
  15.  
  16. bool safe(int arr[][n] , int r , int c) {
  17. 	return (r >= 0 && c >= 0 && r < n && c < n && arr[r][c] == -1);
  18. }
  19.  
  20. bool neighbour(int r , int c , int sr , int sc) {
  21. 	for (int i = 0 ; i < n ; ++i)
  22. 		if ((r + x_move[i] == sr) && (c + x_move[i] == sc))
  23. 			return true;
  24. 	return false;
  25. }
  26.  
  27. int depth(int arr[][n] , int r , int c) {
  28. 	int co = 0;
  29. 	for (int i = 0 ; i < n ; ++i)
  30. 		if (safe(arr , r + x_move[i] , c + y_move[i]))
  31. 			c++;
  32. 	return c;
  33. } 
  34.  
  35. bool next_one(int arr[][n] , int *r , int *c) {
  36. 	int nr , nc; 
  37. 	int min_dep_index = -1;
  38. 	int min_dep = n + 1;
  39. 	int k;
  40. 	int s = rand() % n;
  41. 	for (int co = 0 ; co < n ; ++co) {
  42. 		int i = (s + co) % n;
  43. 		nr = *r + x_move[i];
  44. 		nc = *c + y_move[i];
  45. 		k = depth(arr , nr , nc);
  46. 		if (safe(arr , *r , *c) && k < min_dep) {
  47. 			min_dep_index = i;
  48. 			min_dep = k;
  49. 		}
  50. 	}
  51. 	if (min_dep_index == -1)
  52. 		return false;
  53. 	nr = *r + x_move[min_dep_index];
  54. 	nc = *c + y_move[min_dep_index];
  55. 	arr[nr][nc] = arr[*r][*c] + 1;
  56. 	*r = nr;
  57. 	*c = nc;
  58. 	return true;
  59. }
  60.  
  61. bool foo(int arr[][n]) {
  62.     for (int i = 0 ; i < n ; ++i)
  63. 		for (int j = 0 ; j < n ; ++j)
  64. 			arr[i][j] = -1;
  65. 	int r , c , sr , sc;
  66. 	sc = rand() % n;
  67. 	sr = rand() % n;
  68. 	r = sr;
  69. 	c = sc;
  70. 	arr[r][c] = 1;
  71. 	for (int i = 0 ; i < n*n ; ++i) {
  72. 		if (next_one(arr , &r , &c) == false)
  73. 			return false;
  74. 	}
  75. 	if (!neighbour(r , c , sr , sc))
  76. 		return false;
  77. 	print(arr);
  78. 	return true;
  79. }
  80.  
  81. int main() {
  82. 	int arr[n][n];
  83. 	srand(time(nullptr));
  84. 	while (foo(arr) == false) {
  85. 	;
  86. 	}
  87. 	return 0;
  88. }
Time limit exceeded #stdin #stdout 5s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XMWuV3
language:
C++ (gcc 8.3)
created:
6 years 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!