Battleship

You're given a Board that hides a fleet of ships on an n × n grid. Your solution has to fire shots until every ship is sunk, tracking each shot it takes. Every call to check_shot(row, col) returns one of three results. A HIT means there's a ship cell there and it's not yet destroyed. A SUNK means the shot was the last cell of a ship. A MISS means the cell is empty water. Firing at a cell you already fired at returns MISS too, and still counts as a shot.

Your goal is, given a board, to sink all ships in as few shots as possible. There are two tests that ship with the problem and they check different things. The first places the fleet on a 6x6 board and only checks that every ship ends up sunk, no matter how many shots it takes to get there. The second test is the efficiency test, and it runs on a 10x10 board across 20 random layouts, asking your solution to average fewer than 50 shots across those games. In both tests the fleet is the same, a Cruiser and a Submarine, each 3 cells long.

The most natural solution is the one that treats the grid like a nested loop. For every row, walk every column, fire at the cell, record the shot, and stop once every ship is down. There's no strategy here. We're just checking every single cell in reading order.