Missing test case?


  • 0
    A

    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;
        }
    }
    

    }


  • 0
    A

    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.


  • 0

    @alada Thanks, I have added your test case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.