130. 被围绕的区域
给你一个m x n
的矩阵 board
,由若干字符 'X'
和 'O'
,找到所有被 'X'
围绕的区域,并将这些区域里所有的 'O'
用 'X'
填充。
示例 1:
输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] 输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] 解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的'O'
都不会被填充为'X'
。 任何不在边界上,或不与边界上的'O'
相连的'O'
最终都会被填充为'X'
。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
示例 2:
输入:board = [["X"]] 输出:[["X"]]
提示:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]
为'X'
或'O'
解析:
求连通区域的行列的最值即可
class Solution { public: vector<pair<int, int> > rute; int n, m; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool vis[210][210]; void dfs(vector<vector<char> > &board, int u, int v, int& maxu, int& maxv, int &minu, int &minv) { vis[u][v] = 1; maxu = max(maxu, u); maxv = max(maxv, v); minu = min(minu, u); minv = min(minv, v); rute.push_back(pair<int, int> (u, v)); for(int i = 0; i < 4; i++) { int tu = u + dir[i][0]; int tv = v + dir[i][1]; if(tu < 0 || tv < 0 || tu >= n || tv >= m || board[tu][tv] == 'X' || vis[tu][tv]) continue; vis[tu][tv] = 1; dfs(board, tu, tv, maxu, maxv, minu, minv); } } void solve(vector<vector<char>>& board) { n = board.size(); m = board[0].size(); memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(board[i][j] == 'O' && vis[i][j] == 0) { vis[i][j] = 1; rute.clear(); int maxu = i, maxv = j, minu = i, minv = j; dfs(board, i, j, maxu, maxv, minu, minv); if(maxu < n - 1 && maxv < m - 1 && minu > 0 && minv > 0) { for(int k = 0; k < rute.size(); k++) board[rute[k].first][rute[k].second] = 'X'; } } } } } };
标签:tu,区域,int,围绕,vis,130,board,minu,minv From: https://www.cnblogs.com/WTSRUVF/p/16663861.html