首页 > 代码库 > leetcode[130] Surrounded Regions
leetcode[130] Surrounded Regions
给定一个类似棋盘，有X和O，把X圈住的O变为X例如：
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
其实这题的思路，就是先找到四周的O，然后和四周的O相邻的O全都是不可能转化为X的，我们用另外一个符号标记，那么最后，矩阵中的O就是被圈住的，就需要转化为X，然后其他标记的符号就要转为原来的O。这个叫做DFS。
class Solution { public: void dfs(vector<vector<char> > &board, int x, int y) { if(x<0 || x>=board.size() || y<0 || y>=board[0].size() || board[x][y]!=‘O‘) return; board[x][y]=‘#‘; dfs(board, x-1,y); dfs(board, x+1,y); dfs(board, x,y-1); dfs(board, x,y+1); } void solve(vector<vector<char> > &board) { if (board.size() < 3) return ; if (board[0].size() < 3) return ; int m = board.size(), n = board[0].size(); for(int j=0;j<n;j++) { dfs(board,0,j); dfs(board,m-1,j); } for(int i=1;i<m-1;i++) { dfs(board,i,0); dfs(board,i,n-1); } for(int i=0;i<m;i++) for(int j=0;j<n;j++) { if(board[i][j]==‘O‘) board[i][j]=‘X‘; else if(board[i][j]==‘#‘) board[i][j]=‘O‘; } }};
代码就是对上下左右每个边开始DFS解决。可是会栈溢出，哎，这个error略高级，一直摸不清。
如果把DFS的函数改为如下的形式，就可以AC了。
不同之处就是上面的dfs中判断了上下左右，而下面这个的上下左右是在主函数里，dfs是对内层处理。
class Solution { public: void dfs(vector<vector<char>> &board, int i, int j) { int row = board.size(), col = board[0].size(); if(i > 1 && board[i-1][j] == ‘O‘) { board[i-1][j] = ‘#‘; dfs(board, i-1, j); } if(i < row-1 && board[i+1][j] == ‘O‘) { board[i+1][j] = ‘#‘; dfs(board, i+1, j); } if(j > 1 && board[i][j-1] == ‘O‘) { board[i][j-1] = ‘#‘; dfs(board, i, j-1); } if(j < col-1 && board[i][j+1] == ‘O‘) { board[i][j+1] = ‘#‘; dfs(board, i, j+1); } } void solve(vector<vector<char> > &board) { if (board.size() < 3) return ; if (board[0].size() < 3) return ; int m = board.size(), n = board[0].size(); for(int j=0;j<n;j++) { if (board[0][j] == ‘O‘) { board[0][j] = ‘#‘; dfs(board,0,j); } if (board[m-1][j] == ‘O‘) { board[m-1][j] = ‘#‘; dfs(board,m-1,j); } } for(int i=1;i<m-1;i++) { if (board[i][0] == ‘O‘) { board[i][0] = ‘#‘; dfs(board,i,0); } if (board[i][n-1] == ‘O‘) { board[i][n-1] = ‘#‘; dfs(board,i,n-1); } } for(int i=0;i<m;i++) for(int j=0;j<n;j++) { if(board[i][j]==‘O‘) board[i][j]=‘X‘; else if(board[i][j]==‘#‘) board[i][j]=‘O‘; } }};
改天再试试BFS
leetcode[130] Surrounded Regions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。