拦截网站做跳转,建设考试网站,贺州市住房与城乡建设局网站,东莞建设网雅园新村第20期名单公题目链接#xff0c;描述
https://www.lintcode.com/problem/1410
给一个二维矩阵#xff0c;每个grid的值代表地势的高度。水流只会沿上下左右流动#xff0c;且必须从地势高的地方流向地势低的地方。视为矩阵四面环水#xff0c;现在从(R,C)处注水#xff0c;问水能否…题目链接描述
https://www.lintcode.com/problem/1410
给一个二维矩阵每个grid的值代表地势的高度。水流只会沿上下左右流动且必须从地势高的地方流向地势低的地方。视为矩阵四面环水现在从(R,C)处注水问水能否流到矩阵外面去输入的矩阵大小为n x n n 200。
保证每个高度均为正整数。
样例
样例1输入:
mat
[[10,18,13],[9,8,7],[1,2,3]
] and R 1, C 1
输出: YES
解释:
(1,1) → (1,2)→ 流出。
样例2输入:
mat
[[10,18,13],[9,7,8],[1,11,3]
] and R 1, C 1
输出: NO
解释:
从(1,1)无法流向任何其他格点故无法流出去。思路
前置知识BFSQueue
参考代码
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) {//BFSint n matrix.length,mmatrix[0].length;Queueint[] queue new LinkedList();queue.add(new int[]{r,c});int[][] dirs {{-1,0},{1,0},{0,-1},{0,1}};while (!queue.isEmpty()){int[] poll queue.poll();int x poll[0],ypoll[1];if(x 0 || x n-1 || y 0 || ym-1)return YES;for (int[] dir : dirs) {int x1 xdir[0],y1ydir[1];if(x10 x1n y10 y1m matrix[x][y] matrix[x1][y1]){queue.add(new int[]{x1,y1});}}}return NO;}
}
