## Algorithm

Problem Statement for Algrid

### Problem Statement

Algrid is a program that uses a single grid with cells colored white or black as input and returns a new one as output. The grid has H rows and W columns. The topmost row is row 0, the bottommost row is row H-1, the leftmost column is column 0 and the rightmost column is column W-1. The cell at row i, column j can be denoted as (i,j). The program works by evaluating pairs of contiguous cells and making decisions depending on their contents. The following pseudo-code describes how the program works:

```For i = 0 to H-2:
For j = 0 to W-2:
//Get the current colors of cells (i,j) and (i,j+1)
A = Color(i,j) , B = Color(i,j+1)

If (A,B) == (White, White) Then:
Do nothing.
EndIf
If (A,B) == (Black, White) Then:
Repaint cells (i+1,j) and (i+1,j+1) Black.
EndIf
If (A,B) == (White, Black) Then:
Repaint cells (i+1,j) and (i+1,j+1) White.
EndIf
if (A,B) == (Black, Black) Then:
Swap the colors in cells (i+1,j) and (i+1,j+1).
EndIf
EndFor
EndFor
```

You will be given a possible output for the program as a String[] output. The j-th character in the i-th element of output represents the color of cell (i,j) where 'W' represents white and 'B' represents black. Find an input grid that would yield output as a result. If there is more than one possible result, find the lexicographically smallest one. Return the found grid as a String[] following the same format as the input. If there are no grids that would generate the wanted output, return an empty String[] instead.

### Definition

 Class: Algrid Method: makeProgram Parameters: String[] Returns: String[] Method signature: String[] makeProgram(String[] output) (be sure your method is public)

### Notes

- To compare two String[]s A and B, find the smallest index i such that A[i] and B[i] differ. If A[i] is lexicographically smaller than B[i], we say that A is lexicographically smaller than B, and vice versa.
- To compare two Strings C and D, find the smallest index i such that the characters C[i] and D[i] differ. If C[i] is smaller in ASCII ordering than D[i], we say that C is lexicographically smaller than D, and vice versa.

### Constraints

- output will contain between 2 and 16 elements, inclusive.
- Each element of output will contain between 2 and 16 characters, inclusive.
- All elements of output will have the same length.
- Each element of output will only contain 'W' or 'B' characters.

### Examples

0)

 ```{"WWWWWWW", "WWWWWWB", "BBBBBWW"}```
`Returns: {"WWWWWWW", "WWWWWWB", "BBBBBBB" }`
 The following is another input grid that would yield the same output but is not the wanted result as it is not the lexicographically smallest: ```WWWWWWW WWWWWWB BBBBBWB ```
1)

 ```{"BBBBB", "WBWBW"}```
`Returns: {"BBBBB", "WWBWB" }`
2)

 ```{"BBBB", "BBBB", "BBWB", "WWBB", "BWBB"}```
`Returns: { }`
 There is no possible input that would generate this output.
3)

 ```{"WWBBBBW", "BWBBWBB", "BWBBWBW", "BWWBWBB"}```
`Returns: {"WWBBBBW", "BBBBBWB", "BBBBBBB", "BBBWBBB" }`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>

using namespace std;

class Algrid {
public:
vector<string> makeProgram(vector < string> output) {
vector<string> ret;
ret.resize(output.size());
ret[0] = output[0];

for(int i = 0; i < output.size() - 1; ++i) {
for(int msk = (1 << output[i].length()) - 1; msk >= -1; --msk) {
if(msk == -1) {
vector<string> ret;
return ret;
}

string s = "";
for(int j = output[i].length() - 1; j >= 0; --j)
s += ((msk >> j) & 1) ? 'B' : 'W';
string ss = s;

for(int j = 0; j < output[i].length() - 1; ++j) {
if(output[i][j] == 'B' && output[i][j + 1] == 'W')
s[j] = s[j + 1] = 'B';
if(output[i][j] == 'W' && output[i][j + 1] == 'B')
s[j] = s[j + 1] = 'W';
if(output[i][j] == 'B' && output[i][j + 1] == 'B')
swap(s[j], s[j + 1]);
}

if(s == output[i + 1]) {
ret[i + 1] = ss;
break;
}
}
}

return ret;
}
};``````
Copy The Code &

Input

cmd
{"WWWWWWW", "WWWWWWB", "BBBBBWW"}

Output

cmd
{"WWWWWWW", "WWWWWWB", "BBBBBBB" }