Tiny bishops P53547


pdf   zip


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 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.


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

    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
    2 9
    500 1000 500 1000 1000 1000 500 1000 500
      X    X   0    X    0    0   0  500   0


    Case 1: yes
    Case 2: no
    Case 3: no
    Case 4: yes
    Case 5: yes
  • Information
    Salvador Roura
    Official solutions
    C++ Python
    User solutions
    C++ Python
    Cinquè Concurs de Programació de la UPC - Final