We consider a famous game for children in a two dimensional grid: the battleship... where each player wants to sink the fleet of the other player. Instead of considering only segments as ships, we consider that the shape S of a ship is unique and given. It can be for instance a given polyomino or even a disconnected shape. We focus our attention on the strategies that can be used once that the ship has been hit a first time. While the player knows the shape S, which position of S has been hit is not known. Then the goal is to sink the ship using as few shots as possible, that is, by minimizing the number of missed shots. The best shooting strategies to determine the position of the ship and sink it with a minimum number of misses are highly dependent on the shape S... and for each shooting algorithm $alg$, depending on the position of the ship, the number of misses can from a minimum to a maximum max(alg). We call complexity of the shape and denote c(S) the minimum of max(alg) among all shooting algorithm. Then any shooting algorithm provides an upper bound on the complexity of S.

We prove three bounds on c(S), each considering a different class of shapes. By denoting n the cardinbality of the shape, we have c(S) ≤ n-1 for arbitrary shapes and the bound is tight for parallelogram-free shapes. Second, we provide a shooting algorithm that shows that c(S) = O(log n) if S is an HV-convex polyomino. Third, we provide an algorithm that shows that c(S) = O(log log n) if S is a digital convex set. This last result is obtained through a novel discrete version of the Blaschke-Lebesgue inequality relating the area and the width of any convex body.