首页 > 代码库 > leetcode-surrounded regions-ZZ
leetcode-surrounded regions-ZZ
Problem Statement (link):
Given a 2D board containing
A region is captured by flipping all
For example,
‘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 XX O O XX X O XX O X X
After running your function, the board should be:
X X X XX X X XX X X XX O X X
Analysis:
Rather than recording the 2D positions for any scanned ‘O‘, a trick is to substitute any border ‘O‘s with another character - here in the Code I use ‘Y‘. And scan the board again to change any rest ‘O‘s to ‘X‘s, and change ‘Y‘s back to ‘O‘s.
We start searching ‘O‘ from the four borders. I tried DFS first, the OJ gives Runtime error on the 250x250 large board; In the Sol 2 below, I implement BFS instead, and passed all tests.
The time complexity is O(n^2), as in the worst case, we may need to scan the entire board.
Code:
1, DFS
1 class Solution { 2 public: 3 // dfs - Runtime error on large board 250x250 4 void dfs(vector<vector<char>> &board, int r, int c) { 5 if (r<0||r>board.size()-1||c<0||c>board[0].size()-1||board[r][c]!=‘O‘) 6 return; 7 board[r][c]=‘Y‘; 8 dfs(board, r-1, c); 9 dfs(board, r+1, c);10 dfs(board, r, c-1);11 dfs(board, r, c+1);12 }13 void solve(vector<vector<char>> &board) {14 if (board.empty() || board.size()<3 || board[0].size()<3)15 return;16 int r=board.size();17 int c=board[0].size();18 // dfs from boundary to inside19 for (int i=0; i<c; i++) {20 if (board[0][i]==‘O‘)21 dfs(board, 0, i); // first row22 if (board[c-1][i]==‘O‘)23 dfs(board, c-1, i); // last row24 }25 for (int i=0; i<board.size(); i++) {26 if (board[i][0]==‘O‘)27 dfs(board, i, 0); // first col28 if (board[i][c-1])29 dfs(board, i, c-1); // last col30 }31 // scan entire matrix and set values32 for (int i=0; i<board.size(); i++) {33 for (int j=0; j<board[0].size(); j++) {34 if (board[i][j]==‘O‘)35 board[i][j]=‘X‘;36 else if (board[i][j]==‘Y‘)37 board[i][j]=‘O‘;38 }39 }40 }41 };
2, BFS
1 class Solution { 2 public: 3 void solve(vector<vector<char>> &board) { 4 if (board.empty() || board.size()<3 || board[0].size()<3) 5 return; 6 int r=board.size(); 7 int c=board[0].size(); 8 // queues to store row and col indices 9 queue<int> qr;10 queue<int> qc;11 // start from boundary12 for (int i=0; i<c; i++) {13 if (board[0][i]==‘O‘) { qr.push(0); qc.push(i); }14 if (board[r-1][i]==‘O‘) { qr.push(r-1); qc.push(i); }15 }16 for (int i=0; i<r; i++) {17 if (board[i][0]==‘O‘) { qr.push(i); qc.push(0); }18 if (board[i][c-1]==‘O‘) { qr.push(i); qc.push(c-1); }19 }20 // BFS21 while (!qr.empty()) {22 int rt=qr.front(); qr.pop();23 int ct=qc.front(); qc.pop();24 board[rt][ct]=‘Y‘;25 if (rt-1>=0 && board[rt-1][ct]==‘O‘) { qr.push(rt-1); qc.push(ct); } //go up26 if (rt+1<r && board[rt+1][ct]==‘O‘) { qr.push(rt+1); qc.push(ct); } // go down27 if (ct-1>=0 && board[rt][ct-1]==‘O‘) { qr.push(rt); qc.push(ct-1); } // go left28 if (ct+1<c && board[rt][ct+1]==‘O‘) { qr.push(rt); qc.push(ct+1); } // go right29 }30 31 // scan entire matrix and set values32 for (int i=0; i<board.size(); i++) {33 for (int j=0; j<board[0].size(); j++) {34 if (board[i][j]==‘O‘) board[i][j]=‘X‘;35 else if (board[i][j]==‘Y‘) board[i][j]=‘O‘;36 }37 }38 }39 };
http://justcodings.blogspot.com/2014/07/leetcode-surrounded-regions.html
leetcode-surrounded regions-ZZ
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。