Table of Contents
1.Problem
2.Input
3.Output
4.Examples
4.1input
4.2output
5.Code
6.Conclusion
1.Problem
There are many sunflowers in the Garden of the Sun.
Garden of the Sun is a rectangular table with nn rows and mm columns, where the cells of the table are farmlands. All of the cells grow a sunflower on it. Unfortunately, one night, the lightning stroke some (possibly zero) cells, and sunflowers on those cells were burned into ashes. In other words, those cells struck by the lightning became empty. Magically, any two empty cells have no common points (neither edges nor corners).
Now the owner wants to remove some (possibly zero) sunflowers to reach the following two goals:
- When you are on an empty cell, you can walk to any other empty cell. In other words, those empty cells are connected.
- There is exactly one simple path between any two empty cells. In other words, there is no cycle among the empty cells.
You can walk from an empty cell to another if they share a common edge.
Could you please give the owner a solution that meets all her requirements?
Note that you are not allowed to plant sunflowers. You don’t need to minimize the number of sunflowers you remove. It can be shown that the answer always exists.
2.Input
The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1041≤t≤104) – the number of test cases. The description of the test cases follows.
The first line contains two integers nn, mm (1≤n,m≤5001≤n,m≤500) – the number of rows and columns.
Each of the next nn lines contains mm characters. Each character is either ‘X’ or ‘.’, representing an empty cell and a cell that grows a sunflower, respectively.
It is guaranteed that the sum of n?mn?m for all test cases does not exceed 250000250000.
3.Output
For each test case, print nn lines. Each should contain mm characters, representing one row of the table. Each character should be either ‘X’ or ‘.’, representing an empty cell and a cell with a sunflower, respectively.
If there are multiple answers, you can print any. It can be shown that the answer always exists.
4.Examples
4.1input
5
3 3
X.X
…
X.X
4 4
….
.X.X
….
.X.X
5 5
.X…
….X
.X…
…..
X.X.X
1 10
….X.X.X.
twenty two
..
..
4.2output
XXX
..X
XXX
XXXX
.X.X
.X..
.XXX
.X…
.XXXX
.X…
.X…
XXXXX
XXXXXXXXXX
..
..
5.Code
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 505;
int n, m;
char grid[MAX_N][MAX_N];
int result[MAX_N][MAX_N];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; i + + ) {
cin >> (grid[i] + 1);
}
for (int i = 1; i <= n; i + + ) {
for (int j = 1; j <= m; j + + ) {
result[i][j] = 0;
}
}
if (n <= 2) {
for (int i = 1; i <= m; i + + ) {
result[1][i] = 1;
}
if (n == 2) {
for (int i = 1; i <= m; i + + ) {
if (grid[2][i] == 'X') {
result[2][i] = 1;
}
}
}
}
else if (m <= 2) {
for (int i = 1; i <= n; i + + ) {
result[i][1] = 1;
}
if (m == 2) {
for (int i = 1; i <= n; i + + ) {
if (grid[i][2] == 'X') {
result[i][2] = 1;
}
}
}
}
else if (n % 3 == 0) {
for (int i = 2; i <= n; i + = 3) {
for (int j = 1; j <= m; j + + ) {
result[i][j] = 1;
}
}
for (int i = 1; i <= n; i + + ) {
result[i][1] = 1;
}
for (int i = 1; i <= n; i + + ) {
for (int j = 1; j <= m; j + + ) {
if (grid[i][j] != 'X') {
continue;
}
if (i % 3 == 1) {
if (j == 1) {
continue;
}
if (j == 2) {
result[i + 1][2] = 0;
result[i][2] = result[i][3] = 1;
}
else if (j == 4 & amp; & amp; grid[i][j - 2] == 'X') {
result[i + 1][3] = 0;
result[i][4] = 1;
}
else {
result[i][j] = 1;
}
}
else if (i % 3 == 0) {
if (j == 1) {
continue;
}
if (j == 2) {
result[i - 1][2] = 0;
result[i][2] = result[i][3] = 1;
}
else if (j == 4 & amp; & amp; grid[i][j - 2] == 'X') {
result[i - 1][3] = 0;
result[i][4] = 1;
}
else {
result[i][j] = 1;
}
}
}
}
for (int i = 2; i <= n; i + = 3) {
if (result[i - 1][2] & amp; & amp; result[i + 1][2] & amp; & amp; (m < 4 || !(result[i - 1][4] ^ result[i + 1][4]))) {
result[i][1] = 0;
}
}
for (int i = 1; i <= n; i + = 3) {
if (result[i][3] & amp; & amp; !result[i + 1][3]) {
result[i][2] = 1;
}
}
for (int i = 3; i <= n; i + = 3) {
if (result[i][3] & amp; & amp; !result[i - 1][3]) {
result[i][2] = 1;
}
}
}
else {
for (int i = 1; i <= n; i + = 3) {
for (int j = 1; j <= m; j + + ) {
result[i][j] = 1;
}
}
for (int i = 1; i <= n; i + + ) {
result[i][1] = 1;
}
for (int i = 1; i <= n; i + + ) {
for (int j = 1; j <= m; j + + ) {
if (grid[i][j] != 'X') {
continue;
}
if (i % 3 == 0) {
if (j == 1) {
continue;
}
if (j == 2) {
result[i + 1][2] = 0;
result[i][2] = result[i][3] = 1;
}
else if (j == 4 & amp; & amp; grid[i][j - 2] == 'X') {
result[i + 1][3] = 0;
result[i][4] = 1;
}
else {
result[i][j] = 1;
}
}
else if (i % 3 == 2) {
if (j == 1) {
continue;
}
if (j == 2) {
result[i - 1][2] = 0;
result[i][2] = result[i][3] = 1;
}
else if (j == 4 & amp; & amp; grid[i][j - 2] == 'X') {
result[i - 1][3] = 0;
result[i][4] = 1;
}
else {
result[i][j] = 1;
}
}
}
}
for (int i = 4; i < n; i + = 3) {
if (result[i - 1][2] & amp; & amp; result[i + 1][2] & amp; & amp; (m < 4 || !(result[i - 1][4] ^ result[i + 1][4]))) {
result[i][1] = 0;
}
}
for (int i = 3; i <= n; i + = 3) {
if (result[i][3] & amp; & amp; !result[i + 1][3]) {
result[i][2] = 1;
}
}
for (int i = 2; i <= n; i + = 3) {
if (result[i][3] & amp; & amp; !result[i - 1][3]) {
result[i][2] = 1;
}
}
}
for (int i = 1; i <= n; i + + ) {
for (int j = 1; j <= m; j + + ) {
cout << (result[i][j] == 1 ? 'X' : '.');
}
cout << endl;
}
}
return 0;
}
6.Conclusion
The core logic of this code is to determine the placement of characters in the new grid based on the input character grid. The code places characters in the new grid according to certain rules based on the size of the character grid and the character position.
The following is the core logic in the code:1. Read the number of rows and columns of the character grid based on the input.
2. Determine special situations based on the size of the character grid:If the number of rows n is 2 or less, set all characters in the first row to ‘X’, and set the characters in the second row to ‘X’ if necessary.
If the number of columns m is less than or equal to 2, set all characters in the first column to ‘X’, and set the characters in the second column to ‘X’ if necessary.3. For other cases, the rules for placing characters are determined based on the modulo 3 value of the number of lines n:
If n modulo 3 equals 0, the rules are as follows:
Set all characters on line 2 of every 3 lines to ‘X’.
Set the character in column 1 of each row to ‘X’.
Set other characters to ‘X’ based on specific conditions and positions.
If n modulo 3 is not equal to 0, the rules are as follows:
Set all characters on line 1 of every 3 lines to ‘X’.
Set the character in column 1 of each row to ‘X’.
Set other characters to ‘X’ based on specific conditions and positions.4. According to the calculation results, output the corresponding characters in the new grid.
The core logic is based on the size and character position of the input character grid, placing characters in the new grid according to rules. The final output forms a new character grid.
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56070 people are learning the system