Per un gioco come battaglia navale credo che vadano benissimo gli array multidimensionali, utilizzando come tipo di base una struttura che definirai in base alle tue esigenze.