首页 > 代码库 > leetcode——surronded regions
leetcode——surronded regions
时间复杂度: O(n)
空间复杂度:O(n)
题意解析:
就是把所有被“x”包围的“o”替换成 x。所谓 “包围” 是指 上下左右 四个方向,不包括斜上,斜下。。。
算法思路:
没有被“x” 围住: 就是 那一组联通的“o“ 连接到边界了,只要把连接到边界的 ”o“ 替换成*,其他的o就替换成x,最后再把*还原成O
在把连接到边界的O替换成* 用的是bfs,具体代码如下,time:52ms
/* Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X */ class Solution { public: void solve(vector<vector<char>> &board) { int height = board.size(), width; if (height == 0) return; width = board[0].size(); //search the 2 colum (the first colum and the last colum) for (int i = 0; i < height; i++){ if (board[i][0] == 'O') bfs(i, 0, board); if (board[i][width - 1] == 'O') bfs(i, width - 1, board); } //search the first and last rows for (int i = 1; i < width - 1; i++){ if (board[0][i] == 'O') bfs(0, i, board); if (board[height - 1][i] == 'O') bfs(height - 1, i, board); } for (int i = 0; i < height; i++){ for (int j = 0; j < width; j++){ if (board[i][j] == '*'){ board[i][j] = 'O'; } if (board[i][j] == 'O'){ board[i][j] = 'X'; } } } } private: struct position{ int x; int y; }; void bfs(int x, int y, vector<vector<char>> &board){ queue<position> q_pos; visit(x, y, board, q_pos); while (!q_pos.empty()){ auto next_pos = q_pos.front(); q_pos.pop(); visit(x - 1, y, board, q_pos); visit(x + 1, y, board, q_pos); visit(x, y + 1, board, q_pos); visit(x, y - 1, board, q_pos); } } void visit(int x, int y, vector<vector<char>> &board, queue<position> &q_pos){ if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] == 'X') return; if (board[x][y] == 'O'){ board[x][y] = '*'; position p; p.x = x; p.y = y; q_pos.push(p); } } };
leetcode——surronded regions
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。