# BFS-Like solution: go through all candidate.

• ``````// greedy idea, a number can be candidate, only if the up/left number is checked.
// every number is checked out, only consider if the right/ down number can be candidate.
// by this two condidation, we can go through matrix to get the result.
// iterate this process.
// like bfs.
public class Point {
int x, y, value;
Point(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
}
public int kthSmallest4(int[][] matrix, int k) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
Queue<Point> queue = new PriorityQueue<Point>(new Comparator<Point>(){
@Override
public int compare(Point p1, Point p2) {
return p1.value-p2.value;
}
});
int m = matrix.length, n = matrix[0].length;
queue.offer(new Point(0, 0, matrix[0][0]));
int count = 1;
Point p = null;
while (count < k) {
p = queue.poll();
count++;
matrix[p.x][p.y] = Integer.MAX_VALUE;
// right
if (p.y+1 != n && (p.x == 0 || matrix[p.x-1][p.y+1] == Integer.MAX_VALUE))
queue.offer(new Point(p.x, p.y+1, matrix[p.x][p.y+1]));
// down
if (p.x+1 != m && (p.y == 0 || matrix[p.x+1][p.y-1] == Integer.MAX_VALUE))
queue.offer(new Point(p.x+1, p.y, matrix[p.x+1][p.y]));
}
return queue.poll().value;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.