fork download
copy 
  1. /*
  2. QUESTION 8: Knight Rider Paths to Corners
  3.  
  4. Problem Statement:
  5. You are given integer N.
  6. The board size is 2N x 2N.
  7.  
  8. A rider starts at the top-left cell.
  9.  
  10. In one move, the rider moves like a chess knight.
  11.  
  12. You are also given K.
  13. Count the number of distinct paths that reach any corner of the board using at most K moves.
  14.  
  15. Hard Constraints:
  16. 1 <= N <= 10
  17. 1 <= K <= 10
  18.  
  19. Example:
  20. N = 3
  21. K = 2
  22.  
  23. Expected Output:
  24. 1
  25.  
  26. Explanation:
  27. The starting cell is already a corner, so the 0-move path is counted.
  28. No other corner is reached within 2 moves in this example.
  29.  
  30. Brute Force:
  31. Recursively try all knight moves up to K moves.
  32. Count paths that end at a corner.
  33.  
  34. Time Complexity:
  35. O(8^K)
  36.  
  37. Optimized Approach:
  38. Use DP by number of moves.
  39.  
  40. dp[x][y] =
  41. number of ways to stand at cell (x, y) after current moves.
  42.  
  43. For every step, move from each cell to all valid knight positions.
  44. Whenever a corner is reached, add those paths to the answer.
  45.  
  46. Time Complexity:
  47. O(K * N^2)
  48.  
  49. Space Complexity:
  50. O(N^2)
  51. */
  52.  
  53. #include <bits/stdc++.h>
  54. using namespace std;
  55.  
  56. class Solution {
  57. public:
  58.     long long countPaths(int N, int K) {
  59.         int L = 2 * N;
  60.  
  61.         vector<pair<int, int>> moves = {
  62.             {2, 1}, {2, -1}, {-2, 1}, {-2, -1},
  63.             {1, 2}, {1, -2}, {-1, 2}, {-1, -2}
  64.         };
  65.  
  66.         vector<vector<long long>> dp(L, vector<long long>(L, 0));
  67.         dp[0][0] = 1;
  68.  
  69.         long long ans = 1;
  70.  
  71.         auto isTargetCorner = [&](int x, int y) {
  72.             if (x == 0 && y == 0) return false;
  73.  
  74.             return (x == 0 && y == L - 1) ||
  75.                    (x == L - 1 && y == 0) ||
  76.                    (x == L - 1 && y == L - 1);
  77.         };
  78.  
  79.         for (int step = 1; step <= K; step++) {
  80.             vector<vector<long long>> next(L, vector<long long>(L, 0));
  81.  
  82.             for (int x = 0; x < L; x++) {
  83.                 for (int y = 0; y < L; y++) {
  84.                     if (dp[x][y] == 0) continue;
  85.  
  86.                     for (auto [dx, dy] : moves) {
  87.                         int nx = x + dx;
  88.                         int ny = y + dy;
  89.  
  90.                         if (nx >= 0 && nx < L && ny >= 0 && ny < L) {
  91.                             next[nx][ny] += dp[x][y];
  92.                         }
  93.                     }
  94.                 }
  95.             }
  96.  
  97.             for (int x = 0; x < L; x++) {
  98.                 for (int y = 0; y < L; y++) {
  99.                     if (isTargetCorner(x, y)) {
  100.                         ans += next[x][y];
  101.                     }
  102.                 }
  103.             }
  104.  
  105.             dp = next;
  106.         }
  107.  
  108.         return ans;
  109.     }
  110. };
  111.  
  112. int main() {
  113.     Solution sol;
  114.  
  115.     int N = 3;
  116.     int K = 2;
  117.  
  118.     cout << sol.countPaths(N, K) << endl;
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/vnhdT7
language:
C++14 (gcc 8.3)
created:
9 hours 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!