题目
法1:DFS
典型题目,牢记方法!
class Solution { public void solve(char[][] board) { int m = board.length, n = board[0].length; if (m == 0 || n == 0) { return; } boolean[][] visitedO = new boolean[m][n]; // 没有被围绕的'O'位置记录 for (int i = 0; i < n; ++i) { // 首行 dfs(board, visitedO, 0, i, m, n); } for (int i = 0; i < n; ++i) { // 末行 dfs(board, visitedO, m - 1, i, m, n); } for (int i = 0; i < m; ++i) { // 首列 dfs(board, visitedO, i, 0, m, n); } for (int i = 0; i < m; ++i) { // 末列 dfs(board, visitedO, i, n - 1, m, n); } for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (board[i][j] == 'O' && !visitedO[i][j]) { board[i][j] = 'X'; } } } } public void dfs(char[][] board, boolean[][] visitedO, int i, int j, int m, int n) { if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'O' && !visitedO[i][j]) { visitedO[i][j] = true; dfs(board, visitedO, i - 1, j, m, n); dfs(board, visitedO, i + 1, j, m, n); dfs(board, visitedO, i, j - 1, m, n); dfs(board, visitedO, i, j + 1, m, n); } } }