Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
- // OEIS A300665
- // Ricardo Bittencourt, March 11 2018
- #include <iostream>
- #include <vector>
- using namespace std;
- struct Grid {
- Grid(int size) : n(size), grid(size, vector<bool>(size, false)) {
- }
- long long count() {
- return search(0, 0, n);
- }
- long long search(int j, int i, int left) {
- if (left == 1) {
- return 1;
- }
- grid[j][i] = true;
- long long total = 0;
- for (int k = 0; k < 8; k++) {
- int ii = i + di[k];
- int jj = j + dj[k];
- if (ii < 0 || jj < 0 || grid[jj][ii]) {
- continue;
- }
- total += search(jj, ii, left - 1);
- }
- grid[j][i] = false;
- return total;
- }
- int n;
- vector<vector<bool>> grid;
- constexpr static int di[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
- constexpr static int dj[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
- };
- int main() {
- int n;
- cin >> n;
- Grid grid(n);
- cout << grid.count();
- return 0;
- }
Add Comment
Please, Sign In to add comment