When BFS alone isn't enough

I've been trying to solve this problem for a while, and most of the time running into TLE. On the surface it seems a simple BFS. And it is. With the following problem: each BFS takes 10^5. There might be 10^5 test cases. So in total the solution was hitting TLE. 

The epiphany is that you can run the BFS once and store all the possible solutions for later test cases. You can store using a static (class variable) data structure, such as a static Hashtable. Hence only the first test case takes 10^5. All others take O(1). Code is down below, cheers, ACC.

Minimum Knight Moves - LeetCode

1197. Minimum Knight Moves

Medium

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

 

Example 1:

Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

 

Constraints:

• -300 <= x, y <= 300
• 0 <= |x| + |y| <= 300

 

public static Hashtable htKnightMoves = null;
public class Position
{
    public int x;
    public int y;
    public int steps = 0;
    public long key = 0;

    public Position(int x, int y, int steps)
    {
        this.x = x;
        this.y = y;
        this.steps = steps;
        this.key = (long)this.x * (900000 + 7) + this.y;
    }
}
public int MinKnightMoves(int x, int y)
{
    int[] dx = null;
    int[] dy = null;

    if (x > 0 && y > 0)
    {
        dx = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };
        dy = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
    }
    else if (x > 0 && y < 0)
    {
        dx = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
        dy = new int[] { -1, -2, -2, -1, 1, 2, 2, 1 };
    }
    else if (x < 0 && y < 0)
    {
        dx = new int[] { -1, -2, -2, -1, 1, 2, 2, 1 };
        dy = new int[] { -2, -1, 1, 2, 2, 1, -1, -2 };
    }
    else
    {
        dx = new int[] { -2, -1, 1, 2, 2, 1, -1, -2 };
        dy = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };
    }

    if (Solution.htKnightMoves == null)
    {
        Solution.htKnightMoves = new Hashtable();
        Position p = new Position(0, 0, 0);
        Solution.htKnightMoves.Add(p.key, 0);
        Queue queue = new Queue();
        queue.Enqueue(p);
        while (queue.Count > 0)
        {
            Position current = queue.Dequeue();

            for (int i = 0; i < dx.Length; i++)
            {
                Position np = new Position(current.x + dx[i], current.y + dy[i], current.steps + 1);

                if (np.x >= -300 &&
                    np.x <= 300 &&
                    np.y >= -300 &&
                    np.y <= 300 &&
                    Math.Abs(np.x) + Math.Abs(np.y) >= 0 &&
                    Math.Abs(np.x) + Math.Abs(np.y) <= 300 &&
                    !Solution.htKnightMoves.ContainsKey(np.key))
                {
                    Solution.htKnightMoves.Add(np.key, current.steps + 1);
                    queue.Enqueue(np);
                }
            }
        }
    }

    Position pos = new Position(x, y, 0);

    return (int)Solution.htKnightMoves[pos.key];
}