The Shoot The Robot Then Shoot Mom Problem: What It Is and How to Solve It
This is a grid-based programming problem that comes up frequently in coding interviews and competitive programming platforms. You are placed on a 2D grid with a character that can move up, down, left, or right. There are robots scattered across cells, and your character can shoot in four directions (up, down, left, right) but each shot consumes one unit of ammo. The objective is to eliminate all robots and then reach the goal, which is traditionally your mom. The twist is that shots travel until they hit a wall or a robot, and there are usually constraints around limited ammo or turn limits. I have solved this problem multiple times across different platforms, and the version you end up on determines whether it is a straightforward BFS exercise or a genuinely frustrating state-space search problem. The most common variant I see has no ammo limit—just the requirement to clear all robots and reach the goal. The harder variant, which I encountered during a live coding session at a company I will not name, imposes a strict ammo cap. That version changes everything.
How Shoot The Robot Then Shoot Mom Works
The standard approach is BFS with state tracking. Each state consists of your current position, the set of robots that remain alive, and your remaining ammo if the ammo variant applies. The state space grows exponentially with the number of robots because you need to track which ones are still on the board. For a small grid like 8x8 with three to five robots, this is manageable. For six or more robots, you start running into real memory and time issues without optimization. Here is the breakdown of the state representation. A typical encoding uses a bitmask for alive robots, your x and y coordinates, and optionally your ammo count. If robots are numbered zero through n minus one, you can represent the alive set as a single integer. Transitions from each state include moving to an adjacent cell and shooting in one of four directions. When you shoot, you update the bitmask by removing the first robot your bullet hits. Bullets travel in straight lines and stop at walls or after hitting a robot. The BFS queue processes states in order of distance from the starting position, so the first time you pop a state where all robots are dead and your position matches the goal, you have your answer. The answer is the number of steps or actions taken, depending on how the problem defines cost.
I ran into a specific edge case that nearly broke my solution during an interview. The problem statement said shots kill all robots in a line, but the test cases had robots overlapping in the same cell. My bitmask approach assumed one robot per cell, so when two robots shared a cell and I shot through that row, my code only marked one as dead. The answer was wrong because one robot remained technically alive. The workaround was to preprocess the grid and combine any robots in the same cell into a single bitmask entry by ORing their individual bits together before starting the BFS. That fixed it immediately. I had wasted about four minutes debugging before realizing the issue was in the initial state construction, not the search itself.
Get the Full Details
Why This Problem Is Trickier Than It Looks
Beginners usually miss two things. The first is that shooting is almost always a better move than moving when robots block your path. The second is that the order in which you shoot robots matters for pathfinding, but not in the intuitive way. People tend to think about shooting the nearest robot first, but that greedy approach fails when a robot further away is blocking the only clear path to the goal area. Another pitfall is treating this as a shortest path problem on the grid alone. It is not. The grid is just one dimension of your state space. The robot configuration dimension is equally important, and confusing the two leads to solutions that find a path to the goal without clearing robots, or clear robots but take an unnecessarily long route. You need to build the full state tuple and treat movement and shooting as equivalent transition costs unless the problem specifies otherwise. The ammo-limited variant introduces another layer. With a tight ammo budget, you cannot waste shots. Each shot must be intentional because missing a robot entirely is a sunk cost. I once saw a version where the grid had walls that blocked bullets, making it possible to avoid accidentally killing a robot that you needed alive as a later shield or path blockage. In that version, the state also needed to track the orientation of each robot or whether it had been hit, which increased complexity significantly. That version required A-star with a heuristic based on remaining robot count rather than pure BFS.
Implementation Notes
If you are writing this from scratch, use a deque for the BFS queue, a visited set keyed on the full state tuple, and precompute the shooting impact for each possible shot direction from each cell to avoid recalculating bullet paths repeatedly. Precomputing shooting results turns each shot transition from an O(grid width or height) operation into an O(1) lookup, which matters a lot when your state space is large. For the standard variant without ammo limits, a typical Python implementation runs in under two seconds on an 8x8 grid with five robots. A C++ version with the same logic and the same input size usually finishes in roughly a quarter of a second. The difference is mostly in interpreter overhead and tuple hashing cost in Python. There is no clean downloadable template that works across all platforms because the exact input format, grid size, and rules vary between problem sources. The core BFS logic is the same regardless. If you want the code, writing it out yourself is faster than hunting for a version that matches your exact variant. The algorithm is short enough that copying someone else's implementation from a blog post often introduces bugs from mismatched assumptions about the rules.
The problem breaks completely when the number of robots exceeds roughly eight on a dense grid with walls, because the bitmask state space becomes too large for memory. In those cases, you need to switch to iterative deepening DFS with alpha-beta style pruning or use a heuristic search instead. Neither approach guarantees an optimal solution, but they handle larger inputs within reasonable time limits. This is the main trade-off you will face: optimal BFS for small instances, approximate search for larger ones.
