最近在刷LeetCode的时候发现一类和二维矩阵（二维数组）搜索有关的题目，一般使用深度优先或广度优先搜索就可以很好的解决这类题目，这里特意总结一下。
1、剑指 Offer 12. 矩阵中的路径
这是一个典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝解决。
首选，在矩阵中任意选择一个格子作为路径的起点。假设举证中某个格子的字符为ch，并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是ch,那么这个格子不可能处在路径上的第i个位置。如果路径上第i个字符正好是ch，那么到相邻的格子寻找路径上的第i+1个字符。出矩阵边界上的格子以外，其他格子都有上、下、左、右 4个方向可以选择，重复这个过程，知道路径上所有字符都在矩阵中找到相应的位置。
并且为了便于控制一个格子只会被访问一遍，我们可以使用一个和矩阵一样大小的boolean矩阵来标识路径是否已经进入了某个格子。
public class Main{
public boolean exist(char[][] board, String word) {
//判空
if(board==null||board.length==0||board[0]==null||board[0].length==0){
return false;
}
char[] chars=word.toCharArray();
boolean[][] isVisited=new boolean[board.length][board[0].length];
//对二维数组进行遍历，即将任意一个字符作为路径的起点开始向四周搜索
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
//board[i][j]==chars[0] 判断一下当前位置的字符是否可以是路径的起点
//如果可以是起点，那么用dfs()方法搜，看看能不能走通一条路径
if(board[i][j]==chars[0]&&dfs(board,i,j,isVisited,chars,0)){
return true;
}
}
}
return false;
}
//深度优先搜索，判断有无符合的路径，有就返回true,否者返回false
private boolean dfs(char[][] board,int i,int j,boolean[][] isVisited,char[] chars,int index){
//index表示匹配word字符的哪个下标了
if(index==chars.length){
return true;
}
//边界值
//是否已经访问过
//是否board[i][j]!=chars[index] ??
if(i<0||j<0||i>board.length||j>board[0].length||isVisited[i][j]||chars[index]!=board[i][j]){
return false;
}
isVisited[i][j]=true;
//上下左右 四个方向搜索
boolean ret=dfs(board,i+1,j,isVisited,chars,index+1)||
dfs(board,i-1,j,isVisited,chars,index+1)||
dfs(board,i,j+1,isVisited,chars,index+1)||
dfs(board,i,j-1,isVisited,chars,index+1);
//回溯之后，恢复原来的状态
isVisited[i][j]=false;
return ret;
}
}
相信上面代码一看就会，值得说明的一点使用了isVisited来判断是否再次访问，用来标记已经访问过的点。
2、岛屿问题
岛屿问题是一类经典的网格搜索类问题。关于岛屿的题目有：
要求解这道题，我们首先来看如何在网格上做 DFS
如何在网格上做 DFS
网格问题是这样一类搜索问题：有 m \times nm×n 个小方格，组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。这种题目乍一看可能有点麻烦，实际上非常简单，尤其是用 DFS 的方法。题目没有限制的话，我们尽量用 DFS 来写代码。
下面我们一步步地构造出方格类 DFS 的代码。
首先，每个方格与其上下左右的四个方格相邻，则 DFS 每次要分出四个岔：
// 基本的 DFS 框架：每次搜索四个相邻方格
void dfs(int[][] grid, int r, int c) {
dfs(grid, r - 1, c); // 上边相邻
dfs(grid, r + 1, c); // 下边相邻
dfs(grid, r, c - 1); // 左边相邻
dfs(grid, r, c + 1); // 右边相邻
}
但是，对于网格边缘的方格，上下左右并不都有邻居。一种做法是在递归调用之前判断方格的位置，例如位于左边缘，则不访问其左邻居。但这样一个一个判断写起来比较麻烦，我们可以用“先污染后治理”的方法，先做递归调用，再在每个 DFS 函数的开头判断坐标是否合法，不合法的直接返回。同样地，我们还需要判断该方格是否有岛屿（值是否为 1），否则也需要返回。
// 处理方格位于网格边缘的情况
void dfs(int[][] grid, int r, int c) {
// 这是超出了矩阵的边界的情况，直接返回就好了
if (r<0||c<0||r==grid.length||c==grid[0].length) {
return;
}
// 若该方格不是岛屿，直接返回
if (grid[r][c] != 1) {
return;
}
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
之后为了能够让递归停止下来，我们需要在遍历的时候把已经遍历过的网格做一下标记，可以单独开辟一个和矩阵同样大小的二维boolean矩阵来记录，或者也可以直接修改遍历过的网格的值使其在下一次判断时条件不成立。
通常考虑到内存友好，我们直接在原数组上标记就好了。标记遍历过的方格并不需要使用额外的空间，只需要改变方格中存储的值就可以。在这道题中，值为 0 表示非岛屿（不可遍历），值为 1 表示岛屿（可遍历），我们用 2 表示已遍历过的岛屿。
这样我们就可以得到网格 DFS 遍历的框架代码：
// 处理方格位于网格边缘的情况
void dfs(int[][] grid, int r, int c) {
// 这是超出了矩阵的边界的情况，直接返回就好了
// 若该方格不是岛屿，直接返回
if (r<0||c<0||r==grid.length||c==grid[0].length||grid[r][c] != 1) {
return;
}
//将网格标记为已遍历
grid[r][c]=2;
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
岛屿有关的二维数组搜索问题，基本都可以在此框架上修改得到结果。我们来看下面几道经典的题。
2.1 LeetCode200. 岛屿数量
示例：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
对于这个二维矩阵进行遍历，如果来到一个是1的位置，开始一个“感染”过程，就是从当前位置出发，把连成一片的1全部变成2。“感染”过程结束之后，继续遍历二维矩阵，直到结束。有多少次“感染”过程，就有多少个岛。
实现“感染”过程。假设从i行j列位置出发，向上下左右四个位置依次去“感染”。写成递归函数即可。
public class Main{
public int numIslands(int[][] grid){
if(grid==null||grid.length==0||grid[0]==null||grid[0].length==0){
return 0;
}
//数量
int count=0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]==1){
count++;
dfs(grid,i,j);
}
}
}
return count;
}
private void dfs(int[][] grid,int i,int j){
//剪枝
if(i<0||j<0||i==grid.length||j==grid[0].length||grid[i][j]!='1'){
return;
}
grid[i][j]=2;
//上下左右搜素
dfs(grid,i+1,j);
dfs(grid,i-1,j);
dfs(grid,i,j+1);
dfs(grid,i,j-1);
}
}
2.2 LeetCode 695. 岛屿的最大面积
示例:
输入：
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
基本思路和上面相同，只是需要在遍历每个岛屿的时候，使用一个计数器将这个岛屿的陆地数目记录下来返回，然后比较每个岛屿的大小，返回最大的岛屿的面积即可。代码实现上只需做略微改动即可。
public class Main{
public int maxAreaOfIsland(int[][] grid){
if(grid==null||grid.length==0||grid[0]==null||grid[0].length==0){
return 0;
}
int maxArea=0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]==1){
//dfs每次标记出某个岛屿的面积大小，这里保存最大的返回即可
maxArea=Math.max(maxArea,dfs(grid,i,j));
}
}
}
return maxArea;
}
private int dfs(int[][] grid,int i,int j){
if(i<0||j<0||i==grid.length||j==grid[0].length||grid[i][j]!=1){
return 0;
}
int count=1;
grid[i][j]=2;
count+=dfs(grid,i+1,j);
count+=dfs(grid,i-1,j);
count+=dfs(grid,i,j+1);
count+=dfs(grid,i,j-1);
return count;
}
}
2.3 LeetCode 463. 岛屿的周长
示例：
输入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
输出: 16
求岛屿的周长其实有很多种方法，如果用 DFS 遍历来求的话，有一种很简单的思路：岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量。注意，这里的非岛屿方格，既包括水域方格，也包括网格的边界。我们可以画一张图，看得更清晰：
将这个“相邻关系”对应到 DFS 遍历中，就是：每当在 DFS 遍历中，从一个岛屿方格走向一个非岛屿方格，就将周长加 1。完整代码如下：
public class Main{
public int islandPerimeter(int[][] grid){
if(grid==null||grid.length==0||grid[0]==null||grid[0].length==0){
return 0;
}
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]==1){
//题目中限定只有一个岛屿，因此当dfs返回就可以直接返回结果了
//存在多个岛屿，多次调用这个方法就好了
return dfs(grid,i,j);
}
}
}
return 0;
}
private int dfs(int[][] grid,int i,int j){
//边界或者水域区 边长+1
if(i<0||j<0||i==grid.length||j==grid[0].length||grid[i][j]==0){
return 1;
}
//遍历过的区域直接返回
if(grid[i][j]!=1){
return 0;
}
int len=0;
grid[i][j]=2;
len+=dfs(grid,i+1,j);
len+=dfs(grid,i-1,j);
len+=dfs(grid,i,j+1);
len+=dfs(grid,i,j-1);
}
}
那么每一次进行 “深度优先遍历” 或者 “广度优先遍历” 的条件就是：
1、这个格子是陆地 1，如果是水域 0 就无从谈论 “岛屿”；
2、这个格子不能是之前发现 “岛屿” 的过程中执行了 “深度优先遍历” 或者 “广度优先遍历” 操作，而被标记的格子（这句话说得太拗口了，大家意会即可，意会不了不是您的问题，是我表达的问题，直接看代码会清楚很多）。
3、剑指 Offer 13. 机器人的运动范围
示例 ：
输入：m = 2, n = 3, k = 1
输出：3
这个题目和前面对题目类似，也可以看做是一个m×n的矩阵。同样，在这个矩阵中，除了边界上的格子，其他位置的格子都有4个相邻的格子。机器人从(0,0)开始。当他准备移动到(i,j)的时候，首先判断他能否进入，如果他可以进入，则在判断它能否进入4个相邻的格子。
同时这道题还有一个隐藏的优化：我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。如下图，我们展示了 19 * 19 的地图随着限制条件 k 的放大，可行方格的变化趋势，每个格子里的值为行坐标和列坐标的数位之和，绿色方格代表非障碍方格，即其值小于等于当前的限制条件 k。我们可以发现随着限制条件 k 的增大，(0, 0) 所在的绿色方格区域内新加入的非障碍方格都可以由上方或左方的格子移动一步得到。而其他不连通的黄色方格区域会随着 k 的增大而连通，且连通的时候也是由上方或左方的格子移动一步得到，因此我们可以将我们的搜索方向缩减为向右或向下。
可以套用岛屿问题中的模板，完整代码如下：
public class Main {
/**
* 机器人从(0,0)开始运动，当他准备进入坐标为(i,j)的格子的时候，应该首先检查一下这个格子机器人
* 能否进入，如果能进入，则再检查(i,j)四周的格子是否可以进入。因此可以使用回溯算法来实现
* @param m 矩阵的行数
* @param n 矩阵的列数
* @param k 给定阈值
* @return 机器人可到的格子数
*/
public static int movingCount(int m, int n, int k) {
if(m<=0||n<=0||k<0){
return 0;
}
boolean[][] visited=new boolean[m][n];
return dfs(m,n,k,0,0,visited);
}
private static int dfs(int rows, int cols, int k, int i, int j, boolean[][] visited) {
if(i<0||j<0||i==rows||j==cols||visited[i][j]||checkDigitSum(i,j,k)){
return 0;
}
int count=1;
visited[i][j]=true;
//向下，向右搜索即可
count+=dfs(rows, cols, k, i+1, j, visited);
//count+=dfs(rows, cols, k, i-1, j, visited);
count+=dfs(rows, cols, k, i, j+1, visited);
//count+=dfs(rows, cols, k, i, j-1, visited);
return count;
}
//检查坐标各个位之和是否大于k
private static boolean checkDigitSum(int i, int j, int k) {
return getDigitSum(i)+getDigitSum(j)>k;
}
//分解一个数字的各个位并求他们的和
private static int getDigitSum(int num) {
int sum=0;
while (num>0){
sum+=num%10;
num/=10;
}
return sum;
}
}
