Kth Largest element of a sorted matrix

/**Given a N*N Matrix. 
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.

- 646 on November 23, 2010 | Report Duplicate */

/**For me, it is easier to think of the P-th smallest element
and then use K = N*N-P
For example we have a 4*4 matrix:
1   10 19 20
2   22 30 40
21  30 40 50
39  40 50 60
The numbers are trivial, but the orders and the positions are important.

[0,0] is the smallest.
Ignore the boundary case for now. Every element has two definite directions:
going right or down, which results a larger number.

It is simpler than Dajikstra, we only need to keep the unvisited frontier 
elements in a priority queue. Every time we pop an element, mark it visited,
and immediately push in its two neighbors, i.e. right and down neighbors.
*/
/**In C++, the default priorit_queue is a max heap, especially when less-than
is defined.
*/
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <iostream>
#include <array>
using namespace std;
template <typename T>
class Solution{
  typedef tuple<T, int, int> Element;
  class ElementMore{
  public:
    bool operator() (const Element& lhs, const Element& rhs) const{
      return get<0>(lhs) > get<0>(rhs);
  }
  };//class ElementLess
public: 
  T getSmallRank(vector<vector<T>> const& matrix, int const k){
    if (matrix.empty()) return 0;
    int const N = matrix.size();
    if (N != matrix[0].size()) return 0;//not a square matrix
    if (k < 1 || k > N*N) return 0;
    //k is the desired rank to return
    vector<vector<T>> visitFlag;
    visitFlag.resize(matrix.size());
    for(auto it = visitFlag.begin(); it != visitFlag.end(); ++it) it->resize(matrix.size());
    //init visitFlag to all 0. label 1 for visited
    Element element = make_tuple(matrix[0][0], 0, 0);//<value, row, col>
    priority_queue<Element, vector<Element>, ElementMore> frontier;
    frontier.push(element);
    visitFlag[0][0] = 1;
    for(int rank = 1; rank < k; ++rank){
      element = frontier.top(); frontier.pop();
      int const row = get<1>(element);
      int const col = get<2>(element);
      if (col + 1 < N && !visitFlag[row][col+1]){//element has a right neighbor
        frontier.push(make_tuple(matrix[row][col+1],row,col+1));
        visitFlag[row][col+1] = 1;
      }//right neighbor
      if (row + 1 < N && !visitFlag[row+1][col]){//has a down neighbor
        frontier.push(make_tuple(matrix[row+1][col],row+1,col));
        visitFlag[row+1][col] = 1;
      }//down neighbor
    }//for rank
    return get<0>(frontier.top());
  }//getSmallRankP

  T getBigRank(vector<vector<T>> const& matrix, int const k){
    return getSmallRank(matrix, matrix.size()*matrix.size()-k+1);
  }

};

int main(){
  cout<<"HEllo"<<endl;
  array<int, 4> a = {1 ,  10, 19, 20};
  array<int, 4> b = {2 ,  22, 30, 40};
  array<int ,4> c = {21,  33, 40, 50};
  array<int, 4> d = {39,  40, 51, 60};
  //ranks:        1 ,2, 3,  4,  5,  6, 7
  //elements:     1 ,2, 10, 19, 20, 21,22
  //and rank 15 is 51
  //and rank 16 is 60
  vector<vector<int>> matrix;
  matrix.resize(4);
  matrix[0].assign(a.begin(),a.end());
  matrix[1].assign(b.begin(),b.end());
  matrix[2].assign(c.begin(),c.end());
  matrix[3].assign(d.begin(),d.end());
  Solution<int> s;
  for(int ii = 1; ii <=7; ++ii){
    auto result = s.getSmallRank(matrix,ii);
    cout<<result<<endl;
  }
  cout<< s.getSmallRank(matrix, 15)<<endl<<endl;
  cout<< s.getSmallRank(matrix, 16)<<endl<<endl;
  cout<< s.getBigRank(matrix, 2)<<endl<<endl;

}