這是一道Acceptance不到20%的Medium題躏吊。通常這種情況就是有需要細(xì)心考慮的邊界條件或者遞歸終止條件葫掉。
這題思路的話很容易想目尖，從外圍找O，找到了就用DFS或者BFS之類的把都是O的neighbor賦值成Y勇垛。然后掃兩遍脖母，把O變成X，Y變回O闲孤。
主要看看DFS部分吧谆级，比較典型的floodfill。注意終止條件寫法讼积。
另外網(wǎng)上有很多用用QUEUE實(shí)現(xiàn)了BFS肥照，也該寫寫的，今天太jb累了勤众，真的舆绎，在公司寫了一天膠水代碼，困的一B们颜。睡覺了吕朵。
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int row = board.length;
int col = board[0].length;
for (int i = 0; i < row; i++) {
dfs(board, i, 0, row, col);
if (col > 1)
//這樣的話只有一列的情況不用單獨(dú)處理了
dfs(board, i, col - 1, row, col);
}
//這里可以掐頭去尾
for (int i = 1; i < col - 1; i++) {
dfs(board, 0, i, row, col);
if (row > 1)
dfs(board, row - 1, i , row, col);
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
if (board[i][j] == 'Y') {
board[i][j] = 'O';
}
}
}
private void dfs(char[][] board, int i, int j, int row, int col) {
if (board[i][j] == 'O') {
board[i][j] = 'Y';
// if (i < 0 || i > row - 1 || j < 0 || j > col - 1) return;
if (i - 1 > 0) dfs(board, i - 1, j, row, col);
if (i + 1 < row) dfs(board, i + 1, j, row, col);
if (j - 1 > 0) dfs(board, i, j - 1, row, col);
if (j + 1 < col) dfs(board, i, j + 1, row, col);
}
}
}
DFS猎醇，BFS可以多搜幾種解法看看，比如下面的ref里的幾種努溃；但是我看了很多種解法硫嘶，只有上面貼的這種在檢查下一次dfs是否滿足的寫法才勉強(qiáng)AC（估計(jì)速度也是很慢），其他的都會(huì)stackOverFlow梧税，我一開始覺得是哪里有邏輯問題沦疾，因?yàn)椴籄C的話一般是TLE啊，這題為什么是SOF呢第队。哮塞。〕馄蹋看了http://blog.csdn.net/ChilseaSai/article/details/50375111 之后明白了彻桃，就是典型的遞歸層數(shù)過深產(chǎn)生的啊。晾蜘。每一次遞歸都是一個(gè)棧，Leetcode給出了一些非常屌的testcase眠屎，長達(dá)幾KB的矩陣剔交。。我也是醉了：
所以改衩，同樣是DFS岖常，在下一次運(yùn)行開始之前檢查，和利用終止條件檢查葫督，前者效率會(huì)高于后者（前者從本層就阻止了進(jìn)入下一層DFS竭鞍，后者是進(jìn)入下一層DFS再return）。另外橄镜，對(duì)于數(shù)據(jù)量大的testcase偎快，用BFS。
那如果不考慮那么大的test case洽胶，這題的dfs部分還可以這么寫：
private void dfs(char[][] board, int x, int y, int row, int col) {
if (x >= 0 && x < row && y >=0 && y <col && board[x][y] == 'O') {
board[x][y] = 'Y';
dfs(board, x - 1, y, row, col);
dfs(board, x + 1, y, row, col);
dfs(board, x, y - 1, row, col);
dfs(board, x, y + 1, row, col);
}
}
或者這么寫：
private void dfs(char[][] board, int i, int j, int row, int col) {
if (i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O') return;
board[i][j] = 'Y';
dfs(board, i - 1, j, row, col);
dfs(board, i + 1, j, row, col);
dfs(board, i, j - 1, row, col);
dfs(board, i, j + 1, row, col);
}
總之晒夹，能終止遞歸就可以了。
用BFS的話可以這么寫：
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int row = board.length;
int col = board[0].length;
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O')
bfs(board, i, 0, row, col);
if (col > 1)
if (board[i][col-1] == 'O')
//這樣的話只有一列的情況不用單獨(dú)處理了
bfs(board, i, col - 1, row, col);
}
//這里可以掐頭去尾
for (int i = 1; i < col - 1; i++) {
if (board[0][i] == 'O')
bfs(board, 0, i, row, col);
if (row > 1)
if (board[row-1][i] == 'O')
bfs(board, row - 1, i, row, col);
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
if (board[i][j] == 'Y') {
board[i][j] = 'O';
}
}
}
private void bfs(char[][] board, int i, int j, int row, int col) {
//泛型只能有一個(gè)參數(shù)姊氓，所以這里用了Pair保存坐標(biāo)（也可用余數(shù)和商來解析丐怯，可參考http://blog.csdn.net/ChilseaSai/article/details/50375111）
LinkedList<Pair> queue = new LinkedList<>();
Pair pair = new Pair(i, j);
queue.add(pair);
while (!queue.isEmpty()) {
Pair p = queue.poll();
int x = p.x;
int y = p.y;
//因?yàn)閒loodfill向四個(gè)方向擴(kuò)散，所以可能回到剛才蔓延過的地方翔横；如果不加這句读跷，提交的時(shí)候會(huì)TLE
if (board[x][y] == 'Y') continue;
if (board[x][y] == 'O') {
board[x][y] = 'Y';
}
if (x - 1 >= 0 && board[x - 1][y] == 'O') {
queue.add(new Pair(x - 1, y));
}
if (x + 1 < row && board[x + 1][y] == 'O') {
queue.add(new Pair(x + 1, y));
}
if (y - 1 >= 0 && board[x][y - 1] == 'O') {
queue.add(new Pair(x, y - 1));
}
if (y + 1 < col && board[x][y + 1] == 'O') {
queue.add(new Pair(x, y + 1));
}
}
}
class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
再稍微提一下，遍歷四個(gè)邊的方法還可以這么寫：
//對(duì)所有在邊上的O節(jié)點(diǎn)進(jìn)行BFS
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[0].length;j++) {
if(i==0||i==(board.length-1)||j==0||j==(board[0].length-1)) {
if(board[i][j]=='O') {
Pair position = new Pair(i,j);
queue.add(position);
}
}
}
}
參考的是這里禾唁，復(fù)雜度是一樣的都是O(m*n)效览。
另外些膨，本題還可以用并查集來實(shí)現(xiàn)，leetcode的discussion里有钦铺。
http://blog.sina.com.cn/s/blog_b9285de20101j1dt.html
http://www.cnblogs.com/guyufei/p/3448824.html
http://blog.csdn.net/ChilseaSai/article/details/50375111
