Tiny bishops P53547


Statement
 

pdf   zip

html

Consider an n × m chess board, where some cells are legal and some are prohibited. You have many small bishops, so tiny that an unbounded number of them fit in every cell. As expected, bishops can only move diagonally. For every given board description, tell if there is a way to (repeatedly) move as many bishops as needed, never passing a prohibited cell, so that eventually all the legal cells have the same number of bishops.

Input

Input begins with a number t ≥ 0, followed by t cases. Every case begins with the number of rows n and the number of columns m. Follow n lines, each with m items separated with spaces. Prohibited cells are marked with an ‘X’. For legal cells, its initial number of bishops is given. No cell has more than 1000 bishops. Assume 1 ≤ n, m ≤ 100.

Output

For every case, print its number followed by “yes” or “no”, depending on whether it is possible to move the bishops so that eventually all the legal cells have the same number.

Public test cases
  • Input

    5
    
    3 9
    0 X X X 4 X X X 8
    X 1 X 3 X 5 X 7 X
    X X 2 X X X 6 X X
    
    2 8
    X 1 X 1 X 3 X 3
    X X 1 X X X 3 X
    
    2 2
    X 9
    8 X
    
    1 1
    X
    
    2 9
    500 1000 500 1000 1000 1000 500 1000 500
      X    X   0    X    0    0   0  500   0
    

    Output

    Case 1: yes
    Case 2: no
    Case 3: no
    Case 4: yes
    Case 5: yes
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python
    Event
    Cinquè Concurs de Programació de la UPC - Final
    Date
    2007-10-03