#P14108. [ZJCPC 2017] Domino Tiling

[ZJCPC 2017] Domino Tiling

题目描述

Chiaki has an n×mn \times m rectangular chessboard. She would like to tile this board with dominoes, where a domino is a 2×12 \times 1 rectangle, such that:

  • all the squares of the board are covered but no dominoes overlap or lie partially off the board.
  • there must be no points where corners of four different dominoes meet.

The figure below shows some forbidden configurations:

:::align{center} :::

The figure below shows two valid tilings of 4×44 \times 4 chessboard:

:::align{center} :::

You also need to number the dominoes of chessboard so that no two dominoes have the same number. You can use the number from 11 to n×mn \times m.

输入格式

There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case:

The first line contains two integers nn and mm (1n,m100)(1 \le n, m \le 100) -- the size of the rectangular chessboard.

It is guaranteed that the sum of n×mn \times m over all test cases does not exceed 2×1062 \times 10^6.

输出格式

For each test case, output a valid chessboard described above. A valid chessboard consists of nn lines and each line contains mm integers. Each integer in the output should represent the idid of a domino. The grids sharing the same idid belong to the same domino.

If there is no solution, output "Impossible!"" (without the quotes) instead.

3
1 1
4 3
4 4
Impossible!
1 2 2 
1 3 3 
5 5 4 
6 6 4 
1 1 3 3 
5 7 7 6 
5 8 8 6 
2 2 4 4