Putting Plates solution codeforces
To celebrate your birthday you have prepared a festive table! Now you want to seat as many guests as possible.
The table can be represented as a rectangle with heightand width , divided into cells. Let denote the cell in the -th row and the -th column of the rectangle ( ; ).
Into each cell of the table you can either put a plate or keep it empty.
As each guest has to be seated next to their plate, you can only put plates on the edge of the table — into the first or the last row of the rectangle, or into the first or the last column. Formally, for each cellyou put a plate into, at least one of the following conditions must be satisfied: , , , .
To make the guests comfortable, no two plates must be put into cells that have a common side or corner. In other words, if cellcontains a plate, you can’t put plates into cells , , , , , , , .
Put as many plates on the table as possible without violating the rules above.
The first line contains a single integer( ) — the number of test cases.
Each of the followinglines describes one test case and contains two integers and ( ) — the height and the width of the table.
For each test case, printlines containing characters each. Character in line must be equal to if you are putting a plate into cell , and otherwise.
All plates must be put on the edge of the table. No two plates can be put into cells that have a common side or corner. The number of plates put on the table under these conditions must be as large as possible.
You are allowed to print additional empty lines.
3 3 5 4 4 5 6
10101 00000 10101 0100 0001 1000 0010 010101 000000 100001 000000 101010
For the first test case, example output contains the only way to putplates on the table.
For the second test case, there are many ways to putplates on the table, example output contains one of them.
Putting more thanplates in the first test case or more than plates in the second test case is impossible.
Also read : Wafa Na Raas Aayi Lyrics