Minimum Operations to Reduce X to Zero

Problem is here: Minimum Operations to Reduce X to Zero - LeetCode

From the get-go, the main technique to be used here will be a BFS (Breadth-First-Search). No need to use weights, Dijkstra. Simple BFS should do it. The one, and very important point to bare in mind: when the bug lands on a position P, it does not mean that the bug can never land on P again. Remember that the bug might have come from a forward move, or might have come from a backwards move, and these are distinct, hence when you determine the key to mark P as visited, you actually have two distinct keys:

P + ForwardMove
P + BackwardsMove

Doing so is the key to solving it. Code is down below, cheers, ACC.


public class QueueItem
{
    public int position;
    public bool forwardMove;
    public int steps;
    public int key;

    public QueueItem(int position, bool forwardMove, int steps)
    {
        this.position = position;
        this.forwardMove = forwardMove;
        this.steps = steps;
        this.key = position;
        if (forwardMove) this.key += 10000000;
    }
}
public class Solution
{
    public int MinimumJumps(int[] forbidden, int a, int b, int x)
    {
        Hashtable visited = new Hashtable();
        Queue queue = new Queue();
        QueueItem qi = new QueueItem(0, true, 0);
        queue.Enqueue(qi);
        visited.Add(qi.key, true);

        foreach (int f in forbidden)
        {
            QueueItem qif = null;

            qif = new QueueItem(f, true, 0);
            if (visited.ContainsKey(qif.key)) return -1;
            visited.Add(qif.key, true);
            qif = new QueueItem(f, false, 0);
            if (visited.ContainsKey(qif.key)) return -1;
            visited.Add(qif.key, true);
        }

        while (queue.Count > 0)
        {
            QueueItem current = queue.Dequeue();

            if (current.position == x)
                return current.steps;

            if (current.position <= 10000)
            {
                //Forward
                QueueItem fqi = new QueueItem(current.position + a, true, current.steps + 1);
                if (!visited.ContainsKey(fqi.key))
                {
                    visited.Add(fqi.key, true);
                    queue.Enqueue(fqi);
                }
                if (current.forwardMove)
                {
                    //Backwards
                    QueueItem bqi = new QueueItem(current.position - b, false, current.steps + 1);
                    if (bqi.position >= 0 && !visited.ContainsKey(bqi.key))
                    {
                        visited.Add(bqi.key, true);
                        queue.Enqueue(bqi);
                    }
                }
            }
        }

        return -1;
    }
}

Comments

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

Golang vs. C#: performance characteristics (simple case study)

Advent of Code - Day 7, 2024: Backtracking and Eval