leetcode

0 class Solution {

1 typedef vector<vector<char>> Matrix;

2 typedef queue<pair<int, int>> Queue;

3 const vector<pair<int, int>> offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

4

5 int n, m;

6

7 int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }

8

9 void dfs(Matrix &board, int x, int y) {

10 Queue q;

11

12 q.push({x, y}), board[x][y] = '#';

13 while (!q.empty()) {

14 auto [a, b] = q.front();

15 q.pop();

16 for (auto [oa, ob] : offsets) {

17 int x = a + oa, y = b + ob;

18 if (!valid(x, y) || board[x][y] == 'X' || board[x][y] != 'O') continue;

19 board[x][y] = '#';

20 q.push({x, y});

21 }

22 }

23 }

24

25 public:

26 void solve(Matrix &board) {

27 n = board.size(), m = board[0].size();

28

29 unordered_set<int> convert;

30 Queue q;

31 int group = 0;

32

33 for (int i = 0; i < n; i++) {

34 if (board[i][0] == 'O') dfs(board, i, 0);

35 if (board[i][m - 1] == 'O') dfs(board, i, m - 1);

36 }

37

38 for (int j = 0; j < m; j++) {

39 if (board[0][j] == 'O') dfs(board, 0, j);

40 if (board[n - 1][j] == 'O') dfs(board, n - 1, j);

41 }

42

43 for (int i = 0; i < n; i++)

44 for (int j = 0; j < m; j++)

45 if (board[i][j] != 'X') board[i][j] = board[i][j] == 'O' ? 'X' : 'O';

46 }

47 };