一、基本概念
1.在算法中有一类题型经常出现，通常题目给出一个二维的数组，让你求出有多少条路径？有多少个岛屿？
甚至有些题目给出二维字符数组，让你寻找是否存在某个单词。
这些问题都涉及到递归回溯的相关知识，在此通过leetcode 79. Word Search,和leetcode 200. Number of Islands来进行总结分析。
二、第79题
1.题目：
79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.2.代码及注释：
public class Solution { private int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//这四个数组定义了X和Y可能的移动方向 private int m, n; private boolean[][] visited;//标记这个字母已经走过，不能再重复走 public boolean exist(char[][] board, String word) { if(board == null || word == null) throw new IllegalArgumentException("board or word can not be null!"); m = board.length; if(m == 0) throw new IllegalArgumentException("board can not be empty."); n = board[0].length; if(n == 0) throw new IllegalArgumentException("board can not be empty."); visited = new boolean[m][n]; //每次选择不同的起点，并进行寻路，任何一个起点找到word即可返回true，如果所有起点都找不到，则返回false. for(int i = 0 ; i < m ; i ++) for(int j = 0 ; j < n ; j ++) if(searchWord(board, word, 0, i, j)) return true; return false; } //这个函数用来判断向四个方向移动后的x,y是否越界 private boolean inArea( int x , int y ){ return x >= 0 && x < m && y >= 0 && y < n; } // 从board[startx][starty]开始, 寻找word[index...word.size()) private boolean searchWord(char[][] board, String word, int index, int startx, int starty){ //assert(inArea(startx,starty)); if(index == word.length() - 1) return board[startx][starty] == word.charAt(index); if(board[startx][starty] == word.charAt(index)){ visited[startx][starty] = true; // 从startx, starty出发,向四个方向寻 for(int i = 0 ; i < 4 ; i ++){ int newx = startx + d[i][0]; int newy = starty + d[i][1]; if(inArea(newx, newy) && !visited[newx][newy] && searchWord(board, word, index + 1, newx, newy)) return true; } visited[startx][starty] = false;//某条路径走完，返回上一层走别的路之前都要将visited[][]置为false。 } return false; } // 以下为测试函数 // public static void main(String args[]){ // char[][] b1 = { {'A','B','C','E'}, // {'S','F','C','S'}, // {'A','D','E','E'}}; // String words[] = {"ABCCED", "SEE", "ABCB" }; // for(int i = 0 ; i < words.length ; i ++) // if((new Solution()).exist(b1, words[i])) // System.out.println("found " + words[i]); // else // System.out.println("can not found " + words[i]); // // --- // char[][] b2 = {{'A'}}; // if((new Solution()).exist(b2,"AB")) // System.out.println("found AB"); // else // System.out.println("can not found AB"); // } }三、第200题
1.题目:
200. 岛屿数量
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入: 11110 11010 11000 00000 输出: 1示例 2:
输入: 11000 11000 00100 00011 输出: 32.代码及注释：
class Solution { private int d[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private int m, n; private boolean visited[][]; public int numIslands(char[][] grid) { if(grid == null || grid.length == 0 || grid[0].length == 0) return 0; m = grid.length; n = grid[0].length; visited = 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' && !visited[i][j]){ dfs(grid, i, j);//本次求解的思路类似于深度优先遍历 res ++; } return res; } // 从grid[x][y]的位置开始,进行floodfill // 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地 private void dfs(char[][] grid, int x, int y){ //assert(inArea(x,y)); visited[x][y] = true; for(int i = 0; i < 4; i ++){ int newx = x + d[i][0]; int newy = y + d[i][1]; if(inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1') dfs(grid, newx, newy); //此处与上一题最大的不同在于：visited[][]无需置为false。 } return; } private boolean inArea(int x, int y){ return x >= 0 && x < m && y >= 0 && y < n; } //以下为测试函数： // public static void main(String[] args) { // char grid1[][] = { // {'1','1','1','1','0'}, // {'1','1','0','1','0'}, // {'1','1','0','0','0'}, // {'0','0','0','0','0'} // }; // System.out.println((new Solution()).numIslands(grid1)); // // 1 // // --- // char grid2[][] = { // {'1','1','0','0','0'}, // {'1','1','0','0','0'}, // {'0','0','1','0','0'}, // {'0','0','0','1','1'} // }; // System.out.println((new Solution()).numIslands(grid2)); // // 3 // } }四、总结
通过以上两道题目，可以看出二维数组的寻路、寻词，基本方法就是使用递归回溯，可以简单的理解为试探性前进。以当前起点深入，向下深入，直到到达最后一个位置。如果向下深入发现路已经堵死了，则可以返回上一层，换另一条路。
通常而言，递归回溯的方法都十分好用，但是如果遇到数据量比较大的二维数组，可能运行的时间就会超过预估的时间，这时还要进行适当的剪枝甚至使用动态规划的思维。
之后我还会继续学习，关于动态规划的部分也会成为接下去自己学习的一个重点，加油[< _ >]!
