Depth-First Search (DFS)

Although it is an easy problem and likely there is a clever way to solve it using just mathematical tricks, I decided to do a full implementation of Depth-First Search (DFS). Notice that the "visited" requires you to also use the cardinality of the number of steps taken. Code is down below, cheers, ACC.

Even Number of Knight Moves - LeetCode

You are given two integer arrays start and target, where each array is of the form [x, y] representing a cell on a standard 8 x 8 chessboard.

Return true if a knight can move from start to target in an even number of moves. Otherwise, return false.

Note: A valid knight move consists of moving two squares in one direction and one square perpendicular to it. The figure below illustrates all eight possible moves from a cell.

 

Example 1:

Input: start = [1,1], target = [2,2]

Output: true

Explanation:

One possible sequence of moves is (1, 1) -> (3, 2) -> (2, 4) -> (4, 3) -> (2, 2).

The knight reaches the target in 4 moves, which is even. Thus, the answer is true.

Example 2:

Input: start = [4,5], target = [6,6]

Output: false

Explanation:​​​​​​​

It is impossible to reach target = [6, 6] from start = [4, 5] in an even number of moves. Thus, the answer is false.

 

Constraints:

• start.length == target.length == 2
• 0 <= start[i], target[i] <= 7

public class Solution {
    public bool CanReach(int[] start, int[] target)
    {
        int currentPositionX = start[0];
        int currentPositionY = start[1];
        int targetPositionX = target[0];
        int targetPositionY = target[1];
        int numberOfSteps = 0;
        int minX = 0;
        int minY = 0;
        int maxX = 7;
        int maxY = 7;
        HashSet visitedCardinality = new HashSet();

        int key = currentPositionX * 101 + currentPositionY * 11 + numberOfSteps % 2;
        visitedCardinality.Add(key);

        return _CanReach(currentPositionX, currentPositionY, targetPositionX, targetPositionY, numberOfSteps, minX, minY, maxX, maxY, visitedCardinality);
    }

    private bool _CanReach(int currentPositionX,
                   int currentPositionY,
                   int targetPositionX,
                   int targetPositionY,
                   int numberOfSteps,
                   int minX,
                   int minY,
                   int maxX,
                   int maxY,
                   HashSet visitedCardinality)
    {
        if (currentPositionX == targetPositionX && currentPositionY == targetPositionY)
        {
            return numberOfSteps % 2 == 0;
        }

        int[] movesX = { 1, 1, -1, -1, 2, 2, -2, -2 };
        int[] movesY = { 2, -2, 2, -2, 1, -1, 1, -1 };

        for (int i = 0; i < movesX.Length; i++)
        {
            int newX = currentPositionX + movesX[i];
            int newY = currentPositionY + movesY[i];

            if (newX >= minX &&
                newX <= maxX &&
                newY >= minY &&
                newY <= maxY)
            {
                int key = newX * 101 + newY * 11 + numberOfSteps % 2;
                if (!visitedCardinality.Contains(key))
                {
                    visitedCardinality.Add(key);
                    if (_CanReach(newX, newY, targetPositionX, targetPositionY, numberOfSteps + 1, minX, minY, maxX, maxY, visitedCardinality))
                        return true;
                }
            }
        }

        return false;
    }
}