← 返回题目列表

Codeforces · 1530/B

B. 推杆板

中文机器翻译题面 查看原题

为了庆祝你的生日,你准备了一张节日餐桌!现在您想要容纳尽可能多的客人。

该表格可以表示为一个高度为 $$$h$$$ 和宽度为 $$$w$$$ 的矩形,分为 $$$h \times w$$$ 个单元格。令 $$$(i, j)$$$ 表示矩形第 $$$i$$$ 行和第 $$$j$$$ 列的单元格 ($$$1 \le i \le h$$$; $$$1 \le j \le w$$$)。

在表格的每个单元格中,您可以放置​​一个盘子或将其保留为空。

由于每位客人都必须坐在自己的盘子旁边,因此您只能将盘子放在桌子边缘 - 长方形的第一行或最后一行,或者第一列或最后一列。正式来说,对于放入一块板的每个单元 $$$(i, j)$$$,必须至少满足以下条件之一:$$$i = 1$$$、$$$i = h$$$、$$$j = 1$$$、$$$j = w$$$。

为了让客人感到舒适,不得将两块盘子放入具有共同侧面或共同角的牢房中。换句话说,如果单元格 $$$(i, j)$$$ 包含盘子,则不能将盘子放入单元格 $$$(i - 1, j)$$$, $$$(i, j - 1)$$$, $$$(i + 1, j)$$$, $$$(i, j + 1)$$$, $$$(i - 1, j - 1)$$$, $$$(i - 1, j) + 1)$$$,$$$(i + 1,j - 1)$$$,$$$(i + 1,j + 1)$$$。

在不违反上述规则的情况下,在桌子上放尽可能多的盘子。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

以下 $$$t$$$ 行中的每一行都描述一个测试用例,并包含两个整数 $$$h$$$ 和 $$$w$$$ ($$$3 \le h, w \le 20$$$) - 表格的高度和宽度。

输出

对于每个测试用例,打印 $$$h$$$ 行,每行包含 $$$w$$$ 字符。如果将盘子放入单元格 $$$(i, j)$$$ 中,则 $$$i$$$ 行中的字符 $$$j$$$ 必须等于 $$$1$$$,否则为 $$$0$$$。如果有多个答案,请打印其中一个。

所有盘子必须放在桌子的边缘。不能将两块板放入具有公共侧面或公共角的单元中。在这种情况下,桌上摆放的盘子数量必须尽可能多。

您可以打印额外的空行。

示例

输入 #1

3
3 5
4 4
5 6

输出 #1

10101
00000
10101

0100
0001
1000
0010

010101
000000
100001
000000
101010

注意

对于第一个测试用例,示例输出包含将 $$$6$$$ 盘子放在桌子上的唯一方法。

对于第二个测试用例,有多种方法可以将 $$$4$$$ 盘子放在桌子上,示例输出包含其中一种。

在第一个测试用例中放置超过 $$$6$$$ 板或在第二个测试用例中放置超过 $$$4$$$ 板是不可能的。