#include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; struct UnionFind { vector data; UnionFind(int size) : data(size, -1) {} bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; bool topological_sort(vector> g, vector &order){ int n = g.size(); order.clear(); vector used(n, false); function dfs = [&](int v){ used[v] = true; for(int to : g[v]){ if(!used[to]) dfs(to); } order.push_back(v); }; for(int v = 0; v < n; v++){ if(!used[v]) dfs(v); } reverse(order.begin(), order.end()); vector inv_order(n); for(int i = 0; i < n; i++) inv_order[order[i]] = i; for(int v = 0; v < n; v++){ for(int u : g[v]){ if(inv_order[v] > inv_order[u]) return false; } } return true; } template class Compress{ public: vector data; int offset; Compress(vector data_, int offset=0): offset(offset){ set st; for(T x: data_) st.insert(x); for(T x: st) data.push_back(x); }; int operator[](T x) { auto p = lower_bound(data.begin(), data.end(), x); assert(x == *p); return offset+(p-data.begin()); } T inv(int x){ return data[x-offset]; } int size(){ return data.size(); } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int h, w, n; cin >> h >> w >> n; vector> c(n, vector(n)); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ cin >> c[i][j]; } } UnionFind uf(h*w); auto to_idx = [&](int i, int j){ return i*w+j; }; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(i+1 < h){ if(c[i][j] == c[i+1][j]) uf.unionSet(to_idx(i, j), to_idx(i+1, j)); } if(j+1 < w){ if(c[i][j] == c[i][j+1]) uf.unionSet(to_idx(i, j), to_idx(i, j+1)); } } } vector> g(h*w); vector roots; for(int i = 0; i < h*w; i++) { if(uf.root(i) == i) roots.push_back(i); } auto cp = Compress(roots); int m = cp.size(); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(i+1 < h){ int u = cp[uf.root(to_idx(i, j))]; int v = cp[uf.root(to_idx(i+1, j))]; if(c[i][j] > c[i+1][j]) g[v].push_back(u); if(c[i][j] < c[i+1][j]) g[u].push_back(v); } if(j+1 < w){ int u = cp[uf.root(to_idx(i, j))]; int v = cp[uf.root(to_idx(i, j+1))]; if(c[i][j] > c[i][j+1]) g[v].push_back(u); if(c[i][j] < c[i][j+1]) g[u].push_back(v); } } } vector ord(m); topological_sort(g, ord); int s = ord[0]; vector dp(m, 1); for(int u: ord){ for(int v: g[u]){ chmax(dp[v], dp[u]+1); } } cout << *max_element(dp.begin(), dp.end()) << endl; }