fb pixel

Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms

  • Sea Battle

    notion image
    You’re trying to develop the game “Sea Battle”. At the beginning of this game, each player places some battleships on a board at certain locations. Each battleship spans a straight line from to , where the connecting line between those coordinates is always perpendicular to the sides of the grid.
    As a first step, you’d like to validate the grid to make sure, the users don’t put the battleships too close to each other or even intersect them. Each of the battleships needs to have at least a single cell of water distancing it from another ship. It’s okay to place the battleships next to the border without any water padding between the border and the ship.

    Input

    The first line of the input contains 3 integers n - the number of the battleships (1 ≤ n ≤ 20), w - the width of the battlefield (1 ≤ w ≤ 1000), and h - the height of the battlefield (1 ≤ h ≤ 1000).
    The next n lines contain 4 integers - and (1 ≤ ≤ h) (1 ≤ ≤ w) coordinates of each battleship.

    Output

    The program should print Valid in case the grid is valid and Invalid otherwise.

    Examples

    Input
    Output
    2 10 10 1 1 1 5 8 1 8 10
    Valid
    2 10 10 1 1 1 5 2 3 2 10
    Invalid
     
    To check your solution you need to sign in
    Sign in to continue