130. 被围绕的区域
问题分析：一个矩阵中，如果被包围的区域，原地修改为X
解题思路：先标记边缘的元素为特殊值，然后再全局遍历矩阵，将0-->X，将特殊值-->0
自己第二次做解题出来了，几个堵点注意：
- 遍历标记的时候，注意遍历第一整列和最后一整列，第一行和最后一行要去掉头尾元素
- 做DFS的时候，对于矩阵的遍历，一定要记录访问过的元素
class Solution {public void solve(char[][] board) {int m = board.length;int n = board[0].length;List<int[]> pos = new ArrayList<>();for (int i = 0; i < m; i++) {if (board[i][0] == 'O') {pos.add(new int[] { i, 0 });}if (board[i][n - 1] == 'O') {pos.add(new int[] { i, n - 1 });}}for (int i = 1; i < n - 1; i++) {if (board[0][i] == 'O') {pos.add(new int[] { 0, i });}if (board[m - 1][i] == 'O') {pos.add(new int[] { m - 1, i });}}for (int[] a : pos) {tag(board, a[0], a[1]);}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == 'O') {board[i][j] = 'X';continue;}if (board[i][j] == '2') {board[i][j] = 'O';continue;}}}}private Set<String> visited = new HashSet<String>();private void tag(char[][] board, int i, int j) {if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X') {return;}if (visited.contains(i + "-" + j)) {return;}board[i][j] = '2';visited.add(i + "-" + j);tag(board, i - 1, j);tag(board, i, j + 1);tag(board, i + 1, j);tag(board, i, j - 1);}
}
200. 岛屿数量
刷题步骤，先是5分钟理解题目，确定做题思路，使用什么算法，然后就是编码，编码先使用算法的基本模板，然后根据情况调整
这个题目，使用DFS的方式，结合isVisited来标识是否使用过。
class Solution {public int numIslands(char[][] grid) {// 题目理解清楚// 采取DFS/BFS的方式// 结果是岛屿的数量， int count// 找到所有1的位置// 依次访问visitdint m = grid.length;int n = grid[0].length;boolean[][] isVisited = new boolean[m][n];int res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1' && !isVisited[i][j]) {dfs(grid, isVisited, i, j);res++;}}}return res;}public void dfs(char[][] grid, boolean[][] isVisited, int i, int j) {// 终止条件if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || isVisited[i][j] || grid[i][j] == '0') {return;}isVisited[i][j] = true;dfs(grid, isVisited, i + 1, j);dfs(grid, isVisited, i - 1, j);dfs(grid, isVisited, i, j + 1);dfs(grid, isVisited, i, j - 1);}
}