题目地址：

https://www.lintcode.com/problem/matrix-water-injection/description

给定一个二维矩阵，再给定一个坐标，问从这个坐标出发，是否存在一条严格下降路径能走到矩阵的边界。如果能，则返回"YES"，否则返回"NO"。路径只能每一步向上下左右其中一个方向走一步。

思路是DFS。从该位置出发，尝试其四周更小的数字继续搜索。如果能搜到矩阵边界，则返回"YES"，否则返回"NO"。代码如下：

public class Solution { /** * @param matrix: the height matrix * @param R: the row of (R,C) * @param C: the columns of (R,C) * @return: Whether the water can flow outside */ public String waterInjection(int[][] matrix, int R, int C) { // Write your code here return dfs(R, C, matrix) ? "YES" : "NO"; } private boolean dfs(int x, int y, int[][] matrix) { if (x == 0 || x == matrix.length - 1 || y == 0 || y == matrix[0].length - 1) { return true; } // 搜四个方向 int[] d = {1, 0, -1, 0, 1}; for (int i = 0; i < 4; i++) { int nextX = x + d[i], nextY = y + d[i + 1]; if (0 <= nextX && nextX < matrix.length && 0 <= nextY && nextY < matrix[0].length && matrix[nextX][nextY] < matrix[x][y]) { if (dfs(nextX, nextY, matrix)) { return true; } } } return false; } }

时空复杂度$O(mn)$。

注解： 这里不需要开visited数组记录是否已经访问过，因为这里的DFS是不会走回头路的。