Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct Coord {
- int x;
- int y;
- Coord(int tmp_x, int tmp_y): x(tmp_x), y(tmp_y) {}
- };
- class Solution {
- public:
- void solve(vector<vector<char>>& board) {
- if (board.empty() || board.size() == 0 || board[0].empty() || board[0].size() == 0) return;
- four_ways = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
- for (int i = 0; i < board.size(); i++) {
- for (int j = 0; j < board[0].size(); j++) {
- if (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1) {
- if (board[i][j] == 'O') {
- Coord c(i, j);
- bfs(board, c);
- }
- }
- }
- }
- for (int i = 0; i < board.size(); i++) {
- for (int j = 0; j < board[0].size(); j++) {
- if (board[i][j] == 'O') board[i][j] = 'X';
- else if (board[i][j] == 'Y') board[i][j] = 'O';
- }
- }
- }
- private:
- vector<vector<int>> four_ways;
- void bfs(vector<vector<char>>& board, Coord& c) {
- queue<Coord> Q;
- Q.push(c);
- board[c.x][c.y] = 'Y';
- while(!Q.empty()) {
- Coord tmp_c = Q.front(); Q.pop();
- for (int i = 0; i < 4; i++) {
- Coord new_c(tmp_c.x + four_ways[i][0], tmp_c.y + four_ways[i][1]);
- if (is_valid(board, new_c)) {
- Q.push(new_c);
- board[new_c.x][new_c.y] = 'Y';
- }
- }
- }
- }
- bool is_valid(vector<vector<char>>& board, Coord& c) {
- if (c.x < 0 || c.x >= board.size() || c.y < 0 || c.y >= board[0].size() || board[c.x][c.y] == 'X' || board[c.x][c.y] == 'Y') return false;
- return true;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement