包围区域不适用于较大的输入

-1

我无法让我的代码适用于此问题，我不知道如何找出原因。它适用于小集合，但在大集合失败。包围区域不适用于较大的输入

给定一个包含'X'和'O'的2D板，捕获所有被'X'包围的区域。

通过将所有'O'翻转到包围区域中的'X'来捕获区域。

例如，

X X X X 
X O O X 
X X O X 
X O X X

运行的功能后，主板应该是：

X X X X 
X X X X 
X X X X 
X O X X

我的解决办法：

class Solution { 
public: 

    void solve(vector<vector<char>> &board) { 
     int row = board.size(); 
     if (row<=1) return; 
     int col = board[0].size(); 
     if (col<=1) return; 

     for (int c=0; c<col; c=c+col-1) 
     for (int r=0; r<row; r++) 
     { 
      if (board[r][c]=='O') 
       findBdCoords(board,r, c, row, col); 
     } 

     for (int r=0; r<row; r=r+row-1) 
     for (int c=0; c<col; c++) 
     { 
      if (board[r][c]=='O') 
       findBdCoords(board,r, c, row, col);    
     } 

     for (int r=0; r<row; r++) 
     for (int c=0; c<col; c++) 
     { 
      if (board[r][c]=='O') 
        board[r][c]='x'; 
      if (board[r][c]=='B') 
       board[r][c]='O'; 
     }  
    } 

    void findBdCoords(vector<vector<char>> &board, int r, int c, int row, int col) 
    { 
     if (board[r][c]!='B') 
      board[r][c]='B'; 
       //4 directions neighbor 
         //4 directions neighbor 
      if (r + 1 < row && board[r + 1][c]=='O') 
       findBdCoords(board, r + 1, c, row, col); 

      if (r - 1 >= 0&& board[r - 1][c]=='O') 
       findBdCoords(board, r - 1, c, row, col); 

      if (c + 1<col&& board[r][c + 1]=='O') 
       findBdCoords(board, r, c + 1, row, col); 

      if (c - 1 >= 0&& board[r][c - 1]=='O') 
       findBdCoords(board, r, c - 1, row, col); 
    } 
};

来源

2014-12-02 Happy Coder

综观简单的9x9的，很明显，一个如果触摸边框或连接到触摸边框的O，O不会被包围。

如果我们看一下在边境作为既不是“O”也不是“X”的元素，那么我们可以概括这个规则： 一个“O”不包围，如果它连接到一个“O”与既不是'X'也不是'O'的片段相连接。

我将称这个元素为'B'。

所以，你可以用B的ALA

 BBBBBBBBB 
    BXXXOOXXB 
    BXOXOOXXB 
    BXOOXXXXB 
    BXXXXXXXB 
    BBBBBBBBB

的想法是，即使你把一些B的到中间，你的算法应该仍然工作扩展板。

然后检查一个O单元没有被包围，如果连接到B，好的，否则使用相同的函数检查它的所有O邻居（递归）。

为了加快速度，你可以为你知道连接的任何单元格设置一个标志。这里是伪码，我敢肯定你可以细化它：

CheckCell(location) 
    if connectedLocations[location] return true 
    if checkedLocation[location] return false // This is critical, it stops the infinite spiderweb of neighbor checking. 
    if X return false 
    if B() return true // whatever you decide B is. 
    checkedLocation[location] = true   
    return connectedLocations[location] = CheckCell(north) || CheckCell(south) || CheckCell(east) || CheckCell(west)

来源

2014-12-02 20:04:31

包围区域不适用于较大的输入

回答

相关问题