Guest User

Untitled

a guest
Mar 20th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. // Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
  2. // OEIS A300665
  3. // Ricardo Bittencourt, March 11 2018
  4.  
  5. #include <iostream>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. struct Grid {
  11. Grid(int size) : n(size), grid(size, vector<bool>(size, false)) {
  12. }
  13. long long count() {
  14. return search(0, 0, n);
  15. }
  16. long long search(int j, int i, int left) {
  17. if (left == 1) {
  18. return 1;
  19. }
  20. grid[j][i] = true;
  21. long long total = 0;
  22. for (int k = 0; k < 8; k++) {
  23. int ii = i + di[k];
  24. int jj = j + dj[k];
  25. if (ii < 0 || jj < 0 || grid[jj][ii]) {
  26. continue;
  27. }
  28. total += search(jj, ii, left - 1);
  29. }
  30. grid[j][i] = false;
  31. return total;
  32. }
  33. int n;
  34. vector<vector<bool>> grid;
  35. constexpr static int di[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
  36. constexpr static int dj[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
  37. };
  38.  
  39. int main() {
  40. int n;
  41. cin >> n;
  42. Grid grid(n);
  43. cout << grid.count();
  44. return 0;
  45. }
Add Comment
Please, Sign In to add comment