Why not accepted by BFS ? Facing a long case calling runtime error


  • 0
    S
    void DFS(vector<vector<bool>> &sign, vector<vector<char >> &board, int i, int j)
    {
    	if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size())
    		return;
    	if (sign[i][j] == true || board[i][j] != 'O')
    		return;
    	sign[i][j] = true;
    	DFS(sign, board, i - 1, j);
    	DFS(sign, board, i, j - 1);
    	DFS(sign, board, i, j + 1);
    	DFS(sign, board, i + 1, j);
    }
    void solve(vector<vector<char>> &board)
    {
    	const int m = board.size();
    	if (m == 0) return;
    	const int n = board[0].size();
    	if (m < 3 || n < 3)
    		return;
    	std::vector<vector<bool> > sign(m, vector<bool>(n,false));
    	for (int i = 0; i < n; i++)
    		if (board[0][i] == 'O')
    			DFS(sign, board, 0, i);
    	for (int i = 0; i < n; i++)
    		if (board[m - 1][i] == 'O')
    			DFS(sign, board, m - 1, i);
    	for (int i = 0; i < m; i++)
    		if (board[i][0] == 'O')
    			DFS(sign, board, i, 0);
    	for (int i = 0; i < m; i++)
    		if (board[i][n - 1] == 'O')
    			DFS(sign, board, i, n - 1);
    	for (int i = 0; i < m; i++)
    	{
    		for (int j = 0; j < n; j++)
    		{
    			if (board[i][j] == 'O' && sign[i][j] == false)
    				board[i][j] = 'X';
    		}
    	}
    }

Log in to reply
 

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