C++ using queue and 9ms


  • 0
    X

    class Solution {
    public:

    • void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty())return;
        if (board.size()<3 || board[0].size()<3)return;
        vector<vector<bool>>ChangeBoard(board.size(), vector<bool>(board[0].size(), false));
      queue<std::pair<int, int>>Que;
      int Nrow = board.size(), Ncloumn = board[0].size();
      
      for (int cloumn = 0; cloumn < Ncloumn; cloumn++)
      {
      	if (board[0][cloumn] == 'O') 
      	{
      		ChangeBoard[0][cloumn] = true;
      		Que.push({ 0,cloumn });
      	}
      	if (board[Nrow - 1][cloumn] == 'O')
      	{
      		ChangeBoard[Nrow-1][cloumn] = true;
      		Que.push({ Nrow-1,cloumn });
      	}
      }
      for (int row = 1; row < Nrow-1; row++)
      {
      	if (board[row][0] == 'O')
      	{
      		ChangeBoard[row][0] = true;
      		Que.push({ row,0 });
      	}
      	if (board[row][Ncloumn-1] == 'O')
      	{
      		ChangeBoard[row][Ncloumn-1] = true;
      		Que.push({ row,Ncloumn-1 });
      	}
      }
      int row, cloumn;
      while (!Que.empty())
      {
      	row = Que.front().first;
      	cloumn = Que.front().second;
      	Que.pop();
      	if (row > 0 && board[row - 1][cloumn] == 'O'&& !ChangeBoard[row - 1][cloumn])
      	{
      		ChangeBoard[row - 1][cloumn] = true;
      		Que.push({ row - 1,cloumn });
      	}//up
      	if(row<Nrow-1&& board[row + 1][cloumn] == 'O'&& !ChangeBoard[row + 1][cloumn])
      	{
      		ChangeBoard[row + 1][cloumn] = true;
      		Que.push({ row + 1,cloumn });
      	}//down
      	if (cloumn > 0 && board[row][cloumn - 1] == 'O'&& !ChangeBoard[row][cloumn - 1])
      	{
      		ChangeBoard[row][cloumn - 1] = true;
      		Que.push({ row,cloumn - 1 });
      	}//left
      	if (cloumn<Ncloumn - 1 && board[row ][cloumn + 1] == 'O'&& !ChangeBoard[row][cloumn + 1])
      	{
      		ChangeBoard[row][cloumn + 1] = true;
      		Que.push({ row ,cloumn + 1 });
      	}//right
      }
      
    	for (int row = 1; row<Nrow - 1; row++)
    		for (int cloumn = 1; cloumn<Ncloumn - 1; cloumn++)
    			if (board[row][cloumn] == 'O'&&!ChangeBoard[row][cloumn])board[row][cloumn] = 'X';
    }
    

    };


Log in to reply
 

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