0130.cpp (1404B)
1 class Solution { 2 typedef vector<vector<char>> Matrix; 3 typedef queue<pair<int, int>> Queue; 4 const vector<pair<int, int>> offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 5 6 int n, m; 7 8 int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; } 9 10 void dfs(Matrix &board, int x, int y) { 11 Queue q; 12 13 q.push({x, y}), board[x][y] = '#'; 14 while (!q.empty()) { 15 auto [a, b] = q.front(); 16 q.pop(); 17 for (auto [oa, ob] : offsets) { 18 int x = a + oa, y = b + ob; 19 if (!valid(x, y) || board[x][y] == 'X' || board[x][y] != 'O') continue; 20 board[x][y] = '#'; 21 q.push({x, y}); 22 } 23 } 24 } 25 26 public: 27 void solve(Matrix &board) { 28 n = board.size(), m = board[0].size(); 29 30 unordered_set<int> convert; 31 Queue q; 32 int group = 0; 33 34 for (int i = 0; i < n; i++) { 35 if (board[i][0] == 'O') dfs(board, i, 0); 36 if (board[i][m - 1] == 'O') dfs(board, i, m - 1); 37 } 38 39 for (int j = 0; j < m; j++) { 40 if (board[0][j] == 'O') dfs(board, 0, j); 41 if (board[n - 1][j] == 'O') dfs(board, n - 1, j); 42 } 43 44 for (int i = 0; i < n; i++) 45 for (int j = 0; j < m; j++) 46 if (board[i][j] != 'X') board[i][j] = board[i][j] == 'O' ? 'X' : 'O'; 47 } 48 };