Missing test case?

• My solution got accepted even though it fails the following test case:

["XXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXOOOXXXXXXXX",
"XXXXXOOOXOXOXXXXXXXX",
"XXXXXOXOXOXOOOXXXXXX",
"XXXXXOXOOOXXXXXXXXXX",
"XXXXXOXXXXXXXXXXXXXX"]

The correct answer is the same as the original input, i.e. no change. The solution returns the following instead:

XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX
XXXXXOOOXXXXXXXXXXXX
XXXXXOXOXXXXXXXXXXXX
XXXXXOXOOOXXXXXXXXXX
XXXXXOXXXXXXXXXXXXXX

The solution does a total of 8 passes over all the board elements:

1. First pass turns each border 'O' into a marker character 'a'.
2. Check the rows top-to-bottom. For each row, first go from left to right, marking each 'O' with a neighboring 'a' above or to its left; then go from right to left, marking each 'O' with a neighboring 'a' to its right.
3. Same as #2 but go from bottom to top, and check neighbors below instead of above.
4. Repeat step 2 again.
5. Go over the whole board again to turn all the 'O's to 'X' and 'a's back to 'O'.

Here's the code:

``````void solve(vector<vector<char>> &board) {
int rows = board.size();
int cols = 0;

if (rows > 0) {
cols = board[0].size();
}

if (rows == 0 || cols == 0)
return;

const char o = 'O';
const char x = 'X';
const char a = 'a';

// First mark the boarder '0's. These are
// open and cause their connected '0's to be
// open as well. Use 'a' as the mark.
for (int i = 0; i < rows; ++i) {
if (i == 0 || i == rows-1) {
for (int j = 0; j < cols; ++j) {
if (board[i][j] == o)
board[i][j] = a;
}
} else {
if (board[i][0] == o)
board[i][0] = a;

if (board[i][cols-1] == o)
board[i][cols-1] = a;
}
}

// Traverse rows top-to-bottom, first left-to-right
// then right-to-left.
for (int i = 1; i < rows; ++i) {
// Go from left to right.
// For each 'O', turn into 'a' if its neighbor above
// or to the left is an 'a'.
for (int j = 1; j < cols; ++j) {
if (board[i][j] == o) {
if (board[i-1][j] == a || board[i][j-1] == a) {
board[i][j] = a;
}
}
}

// Now right to left.
// Change each 'O' that has a neighboring 'a' on its right.
for (int j = cols-2; j > 0; --j) {
if (board[i][j] == o && board[i][j+1] == a) {
board[i][j] = a;
}
}
}

// Traverse rows bottom-to-top, again first
// left-to-right then right-to-left.
for (int i = rows-2; i > 0; --i) {
for (int j = 1; j < cols; ++j) {
if (board[i][j] == o) {
if (board[i+1][j] == a || board[i][j-1] == a) {
board[i][j] = a;
}
}
}

for (int j = cols-2; j > 0; --j) {
if (board[i][j] == o && board[i][j+1] == a) {
board[i][j] = a;
}
}
}

// Traverse rows top-to-bottom again.
for (int i = 1; i < rows-1; ++i) {
for (int j = 1; j < cols-1; ++j) {
if (board[i][j] == o) {
if (board[i-1][j] == a || board[i][j-1] == a) {
board[i][j] = a;
}
}
}

for (int j = cols-2; j > 0; --j) {
if (board[i][j] == o && board[i][j+1] == a) {
board[i][j] = a;
}
}
}

for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (board[i][j] == a)
board[i][j] = o;
else if (board[i][j] == o)
board[i][j] = x;
}
}
``````

}

• I later changed the solution such that instead of step 4 described above, I go over each column in both directions. This passes the test case above. So it takes a total of 10 passes.