A solution by bfs


  • 0
    J
    class Solution {
    public:
    	void solve(vector<vector<char>> &board) {
    		if (board.empty()) return;
    		const int m = board.size();
    		const int n = board[0].size();
    		for (int i = 0; i < n; i++) {
    			bfs(board, 0, i);
    			bfs(board, m - 1, i);
    		}
    		for (int j = 1; j < m-1; j++) {
    			bfs(board, j, 0);
    			bfs(board, j, n - 1);
    		}
    		for (int i = 0; i < m; ++i) {
    			for (int j = 0; j < n; ++j) {
    				if (board[i][j] == 'O')
    					board[i][j] = 'X';
    				else if (board[i][j] == '+')
    					board[i][j] = 'O';
    			}
    		}
    	}
    private:
    	typedef struct { int x; int y; } state;
    	void bfs(vector<vector<char>> &board, int i, int j) {
    		queue<state> myq;
    		const int m = board.size();
    		const int n = board[0].size();
    		state start = { i,j };
    		if (is_valid(start, board)) {
    			board[i][j] = '+';
    			myq.push(start);
    		}
    		while (!myq.empty()) {
    			auto cur = myq.front();
    			myq.pop();
    			auto new_states = state_extend(cur, board);
    			for (auto s : new_states) myq.push(s);
    		}
    	}
    	bool is_valid(state &s, vector<vector<char>> &board) {
    		const int x = s.x;
    		const int y = s.y;
    		const int m = board.size();
    		const int n = board[0].size();
    		if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O')
    			return false;
    		return true;
    	}
    	vector<state> state_extend(const state &s, vector<vector<char>> &board) {
    		vector<state> result;
    		const int x = s.x;
    		const int y = s.y;
    		state new_states[4] = { { x - 1,y },{ x + 1,y },
    		{ x,y - 1 },{ x,y + 1 } };
    		for (int i = 0; i < 4; ++i) {
    			if (is_valid(new_states[i], board)){
    				board[new_states[i].x][new_states[i].y] = '+';
    				result.push_back(new_states[i]);
    			}
    		}
    		return result;
    	}
    };
    

Log in to reply
 

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