#include #define REP(i,n) for (int i=0;i<(n);++i) #define all(a) (a).begin(),(a).end() using namespace std; template void amax(T& x, U y) {if (x < y) x = y;} const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; struct edge { typedef size_t weight_type; size_t m_to; edge(size_t to) : m_to(to) { } inline size_t to() const { return m_to; } inline weight_type weight() const { return 1; } friend std::ostream& operator<<(std::ostream &os, const edge &e) { os << "{ to: " << e.m_to << " }"; return os; } }; template struct graph { using edge_type = Edge; const size_t m_n_vertices; std::vector> m_edges; graph(size_t n_vertices) : m_n_vertices(n_vertices), m_edges(n_vertices) { } inline size_t n_vertices() const { return m_n_vertices; } inline void add_edge(size_t from, size_t to, typename edge_type::weight_type weight) { m_edges[from].emplace_back(to, weight); } inline void add_edge(size_t from, size_t to) { m_edges[from].push_back(to); } inline void add_edge(size_t from, const edge_type &e) { m_edges[from].emplace_back(e); } inline void add_biedge(size_t v0, size_t v1, typename edge_type::weight_type weight) { m_edges[v0].emplace_back(v1, weight); m_edges[v1].emplace_back(v0, weight); } inline void add_biedge(size_t v0, size_t v1) { m_edges[v0].push_back(v1); m_edges[v1].push_back(v0); } inline const std::vector& edges_from(size_t v) const { return m_edges[v]; } }; // if g has a cycle, return empty vector. // Time complexity is O(V + E), // where V is the number of vertices, // E is the number of edges. template std::vector topological_sort(const Graph &g) { using Edge = typename Graph::edge_type; std::vector topological_orders(g.n_vertices()); std::vector indegrees(g.n_vertices()); for (size_t v = 0; v < g.n_vertices(); ++v) { for (const Edge &e: g.edges_from(v)) { ++indegrees[e.to()]; } } std::queue q; for (size_t v = 0; v < g.n_vertices(); ++v) { if (!indegrees[v]) { q.push(v); } } for (size_t i = 0; i < g.n_vertices(); ++i) { if (q.empty()) { // has cycle return { }; } size_t u = q.front(); q.pop(); topological_orders[i] = u; for (const Edge &e: g.edges_from(u)) { size_t v = e.to(); --indegrees[v]; if (!indegrees[v]) { q.push(v); } } } return topological_orders; } int main() { cin.tie(0); ios::sync_with_stdio(false); using Graph = graph; int H, W, N; cin >> H >> W >> N; vector> C(H, vector(W)); REP(i, H) REP(j, W) cin >> C[i][j]; Graph g(H * W); REP(i, H) REP(j, W) { REP(k, 4) { int ni = i + dx[k]; int nj = j + dy[k]; if (0 <= ni && ni < H && 0 <= nj && nj < W && C[i][j] < C[ni][nj]) { g.add_edge(i * W + j, ni * W + nj); } } } auto a = topological_sort(g); assert(a.size() == H * W); vector dp(H * W); for (int i : a) { for (const edge &e : g.edges_from(i)) { int j = e.to(); amax(dp[j], dp[i] + 1); } } int result = *max_element(all(dp)) + 1; cout << result << endl; return 0; }