#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; typedef std::pair Pii; typedef std::pair Pll; typedef std::pair Pdd; #define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++) #define all(_l) _l.begin(), _l.end() #define rall(_l) _l.rbegin(), _l.rend() #define MM << " " << template using MaxHeap = std::priority_queue<_T>; template using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>; template inline bool chmax(_T &_l, const _T _b) { if (_b > _l) { _l = _b; return true; } return false; } template inline bool chmin(_T &_l, const _T _b) { if (_l > _b) { _l = _b; return true; } return false; } template void vdeb(const std::vector<_T> &bb) { for (unsigned int i = 0;i < bb.size();i++) { if (i == bb.size() - 1) std::cout << bb[i]; else std::cout << bb[i] << ' '; } std::cout << '\n'; } template void vdeb(const std::vector> &bb) { for (unsigned int i = 0;i < bb.size();i++) { std::cout << i << ": "; vdeb(bb[i]); } std::cout << '\n'; } class UnionFind { int _n; int _size; std::vector par_size; public: UnionFind() :_n(0), _size(0){} UnionFind(int n) : _n(n), _size(n), par_size(n, -1) {} int unite(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); a = root(a), b = root(b); if(a == b) return a; _size--; if(-par_size[a] < -par_size[b]) { par_size[b] += par_size[a]; return par_size[a] = b; } else { par_size[a] += par_size[b]; return par_size[b] = a; } } int root(int a) { assert(0 <= a && a < _n); if(par_size[a] < 0) return a; return par_size[a] = root(par_size[a]); } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return root(a) == root(b); } int size(int a) { assert(0 <= a && a< _n); return -par_size[root(a)]; } int size() {return _size;} std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = root(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } }; using namespace std; int dx[] = {0, 1, 0, -1, 0}; int main() { int h, w, n; cin >> h >> w >> n; vector> da(h, vector(w)); rip(i,h,0) rip(j,w,0) cin >> da[i][j]; auto in_grid = [&](int x, int y) { return 0 <= x && x < h && 0 <= y && y < w; }; auto to_int = [&](int x, int y) { return x*w + y; }; UnionFind uf(h*w); rip(i,h,0) rip(j,w-1,0) if(da[i][j] == da[i][j+1]) { uf.unite(to_int(i, j), to_int(i, j+1)); } rip(i,h-1,0) rip(j,w,0) if(da[i][j] == da[i+1][j]) { uf.unite(to_int(i, j), to_int(i+1, j)); } vector> to_node(h, vector(w)); auto g = uf.groups(); rip(i,g.size(),0) { for(auto j : g[i]) to_node[j/w][j%w] = i; } vector> to(g.size()); vector ot(g.size()); rip(i,h,0) rip(j,w,0) rip(k,4,0) { int nx = i+dx[k], ny = j + dx[k+1]; if(in_grid(nx, ny) && da[i][j] > da[nx][ny]) { to[to_node[i][j]].push_back(to_node[nx][ny]); ot[to_node[nx][ny]]++; } } queue q; rip(i,ot.size(),0) if(ot[i] == 0) q.push(i); vector pot(to.size(), 1); int ans = 1; while(!q.empty()) { auto now = q.front(); q.pop(); ans = pot[now]; for(auto &i : to[now]){ ot[i]--; if(ot[i] == 0) { q.push(i); pot[i] = pot[now] + 1; } } } cout << ans << endl; }