首页 > 代码库 > Surrounded Regions

Surrounded Regions

130. Surrounded Regions

题目链接:https://leetcode.com/problems/surrounded-regions/#/description

题目大意:给定一个二维的板,板上是‘X‘或‘O‘字符,捕获所有被‘X‘包围的区域,在该区域内的字符‘O‘翻转为‘X‘。

 

思路:从板的边界出发,获取边界的所有‘O‘字符的坐标,然后从这些坐标出发,宽度优先搜素所有与边界的‘O‘联通的‘O‘,所有搜索过的‘O‘都修改为字符‘1‘,则宽度优先搜索结束后,所有字符为‘1‘的表示未被字符‘X‘包围的‘O‘,字符为‘O‘的为被‘X‘包围的‘O‘。

代码:

 1 class Solution {
 2 public:
 3     void solve(vector<vector<char>>& board) {
 4         if (board.empty() || board[0].empty())
 5             return;
 6         vector<pair<int, int>> oCoordates;
 7         int row = board.size(), col = board[0].size();
 8         for (int i = 0; i < 2; ++i) {
 9             int x = i ? 0 : row - 1;
10             for (int j = 0; j < col; ++j)
11                 if (board[x][j] == O) {
12                     oCoordates.push_back(make_pair(x, j));
13                     board[x][j] = 1;
14                 }
15         }
16         for (int i = 0; i < 2; ++i) {
17             int y = i ? 0 : col - 1;
18             for (int j = 0; j < row; ++j)
19                 if (board[j][y] == O) {
20                     oCoordates.push_back(make_pair(j, y));
21                     board[j][y] = 1;
22                 }
23         }
24         while (!oCoordates.empty()) {
25             auto coordates = oCoordates.back();
26             oCoordates.pop_back();
27             for (int i = -1; i < 2; i += 2) {
28                 findOCoordates(board, oCoordates, coordates.first, coordates.second + i);
29                 findOCoordates(board, oCoordates, coordates.first + i, coordates.second);
30             }
31 
32         }
33         for (int i = 0; i < board.size(); ++i)
34             for (int j = 0; j < board[0].size(); ++j)
35                 if (board[i][j] == 1)
36                     board[i][j] = O;
37                 else if (board[i][j] == O)
38                     board[i][j] = X;
39     }
40 private:
41     void findOCoordates(vector<vector<char>>& board, vector<pair<int, int>> &oCoordates, int x, int y) {
42         if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == O) {
43             oCoordates.push_back(make_pair(x, y));
44             board[x][y] = 1;
45         }
46     }
47 };

评测系统上运行结果:

技术分享

 

Surrounded Regions