class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int xsize = matrix.size();
int ysize = matrix[0].size();
priority_queue<Node, vector<Node>, Cmp> pq;
pq.push(Node(matrix[0][0], 0, 0));
Node tmp(1, 1, 1);
while(k){
tmp = pq.top();
pq.pop();
if(tmp.i + 1 < xsize){
pq.push(Node(matrix[tmp.i + 1][tmp.j], tmp.i + 1, tmp.j));
}
if(tmp.i == 0 && tmp.j + 1 < ysize){
pq.push(Node(matrix[tmp.i][tmp.j + 1], tmp.i, tmp.j + 1));
}
}
return tmp.val;
}
private:
struct Node {
int val;
int i;
int j;
Node(int vv, int ii, int jj): val(vv), i(ii), j(jj){};
};
struct Cmp {
bool operator()(const Node& a, const Node& b){
return a.val > b.val;
}
};
};
c++ using heap


@quesder
The reason for that is if you do not restrict only when i == 0 that you can push the right neighbor, you may push the same elements for twice. Say, the element can be push by its upper neighbor, and then by its left neighbor.Consider this example:
1 3 5
6 7 12
11 14 14