Problem 5: Sinking Ships
6 Points

In the game of Battleship or Armada, players initially arrange 5 ships on a rectangular grid. The ships are as follows:

Length	Number 
of ship	available
5	1
4	1
3	2
2	1

Ships must be aligned either horizontally or vertically within the grid. Your assignment is to write a program that inputs 
a grid indicating which squares are occupied by ships, and determines whether such a board could be a valid placement 
of the ships described above. Grids will always be 10 squares wide and 10 squares high. Grids will be represented as a 
grid of characters, where O represents an open (unoccupied) square and X marks a square occupied by a ship. End of 
input will be indicated by a line consisting of the string "END". Output for each grid examined should be either "VALID" 
if the grid could represent a legal configuration of the ships described, or "INVALID" if it could not.

Example:

Input
OOOOOOOOOO
OXXXXXOOOO
OOOOOOOOXO
OOXOOOOOXO
OOXOOOOOOO
OOXOOXXXOO
OOOOXOOOOO
OOOOXOOOOO
OOOOXOOOOO
OOOOXOOOOO

OOOOOOOOOO
OOOOOOOXOO
OOXXXXXXOO
OOOOOOOOXO
OOOOOXXXXX
OOOOOOOOXO
OOOOOOXXXO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO

OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
OOOXXXXXOO
OOOXXXXXOO
OOOXXXXXOO
OOOOOOXXOO
OOOOOOOOOO
OOOOOOOOOO
OOOOOOOOOO
END

Output
VALID
INVALID
VALID