マス \((i, j)\) に書かれた整数を \(A[i][j]\) で表します。

動的計画法によってこの問題を解きます。
\(i = 1, 2, \ldots, N\) について、\(\mathrm{dp}[i]\) を下記の通りに定義します。

\(\mathrm{dp}[i] := \)（現在、コマがマス \((r_i, c_i)\) に置かれているとき、それ以降に高橋君がコマの移動を行うことができる回数の最大値）

本問題は、すべての \(i = 1, 2, \ldots, N\) について \(\mathrm{dp}[i]\) の値を求める問題です。よって、これを求める方法を以下で述べます。

現在コマがマス \((r_i, c_i)\) に置かれているとき、コマをマス \((r_j, c_j)\) に移動させることができる必要十分条件は、下記の \(2\) つをともに満たすことです。

• \(A[r_i][c_j] > A[r_i][c_i]\)
• マス \((r_j, c_j)\) はマス \((r_i, c_i)\) と同じ行にある、または、マス \((r_j, c_j)\) はマス \((r_i, c_i)\) と同じ列にある。すなわち、\(r_j = r_i\) または \(c_j = c_i\)

そのようなマス \((r_j, c_j)\) が存在しなければ、マス \((r_i, c_i)\) から移動できるマスはないため、\(\mathrm{dp}[i] = 0\) です。
そのようなマスが存在する場合は、「コマをそのマスに移動した後、それ以降に行うことができる移動の回数が最大となる」ようなマスを移動先に選ぶのが最適です。つまり、

\(\mathrm{dp}[i] = \max\lbrace \mathrm{dp}[j] + 1\) \( | \) マス \((r_i, c_i)\) からマス \((r_j,c_j)\) に移動可能 \(\rbrace\)

です。上記の漸化式を用いることで、すべての \(i = 1, 2, \ldots, N\) について \(\mathrm{dp}[i]\) の値を求めることができます。
ここで、上記の漸化式を用いて \(\mathrm{dp}[i]\) を計算する際には、マス \((r_i, c_i)\) から移動可能なすべてのマス \((r_j, c_j)\) の \(\mathrm{dp}[j]\) の値がすでに求まっている必要があることに注意してください。 このことに関しては、マス \((r_i, c_i)\) からマス \((r_j, c_j)\) に移動可能であるのは \(A[r_i][c_i] < A[r_j][c_j]\) の場合のみに限られるので、\(A[r_i][c_i]\) が大きい \(i\) から順番に \(\mathrm{dp}[i]\) を求めることで解決します。
すなわち、下記のアルゴリズムによって、すべての \(i = 1, 2, \ldots, N\) について \(\mathrm{dp}[i]\) の値を求めることができます。

正整数 \(X\) の降順に以下を行う:

• \(A[r_i][c_i] = X\) を満たすすべてのマス\((r_i, c_i)\)について、 \(\mathrm{dp}[i] \leftarrow \max\lbrace \mathrm{dp}[j] + 1\) \( | \) マス \((r_i, c_i)\) からマス \((r_j,c_j)\) に移動可能 \(\rbrace\) とする。 ただし、\((r_i, c_i)\) から移動可能なマスが存在しない場合は \(\mathrm{dp}[i] \leftarrow 0\)とする。

しかし、上記のアルゴリズムでは最悪の場合に \(\Theta(N^2)\) 時間かかり、実行制限時間に間に合わせることは絶望的です。したがって、これを高速化することを以下で考えます。

ある固定された正整数 \(X\) について、上記アルゴリズム中の

\(A[r_i][c_i] = X\) を満たすすべての \(i\) について、 \(\mathrm{dp}[i] \leftarrow \max\lbrace \mathrm{dp}[j] + 1\) \( | \) マス \((r_i, c_i)\) からマス \((r_j,c_j)\) に移動可能 \(\rbrace\) とする。

を行うことを考えます。 マス \((r_i, c_i)\) から移動可能なマスは、マス \((r_i, c_i)\) と同じ行または同じ列にあるため、\(\mathrm{dp}[i]\) を計算する際には下記の \(2\) つの値がわかっていれば、\(\mathrm{dp}[i]\) はこれら \(2\) つの値の最大値として \(O(1)\) 時間で求められます。

• 「マス \((r_i, c_i)\) から移動可能なマス \((r_j, c_j)\) のうち \(r_i\) 行目にあるもの」の中での \(\mathrm{dp}[j]+1\) の最大値、すなわち、\(\max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, r_j = r_i \rbrace\)
• 「マス \((r_i, c_i)\) から移動可能なマス \((r_j, c_j)\) のうち \(c_i\) 列目にあるもの」の中での \(\mathrm{dp}[j]+1\) の最大値、すなわち、\(\max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, c_j = c_i \rbrace\)

したがって、\(2\) つの配列 \(\mathrm{rmax}[\ast], \mathrm{cmax}[\ast]\) を準備し、\(X\) の降順に \(\mathrm{dp}[\ast]\) の値を求めていく過程において、

• \(r = 1, 2, \ldots H\) のそれぞれについて、\(\mathrm{rmax}[r] = \max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, r_j = r\rbrace\)
• \(c = 1, 2, \ldots W\) のそれぞれについて、\(\mathrm{cmax}[c] = \max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, c_j = c\rbrace\)

を満たす状態を維持することで、\(\mathrm{dp}[i]\) の値を \(\mathrm{dp}[i] \leftarrow \max(\mathrm{rmax}[r_i], \mathrm{cmax}[c_i])\) の通りに \(O(1)\) 時間で求められます。
すなわち、下記のアルゴリズムを用いると、すべての \(i = 1, 2, \ldots, N\) について \(\mathrm{dp}[i]\) の値を高速に求めることができます。

まず、各変数を次のように初期化する。

• すべての \(r =1, 2, \ldots, H\) について、\(\mathrm{rmax}[r] \leftarrow 0\) とする。
• すべての \(c =1, 2, \ldots, W\) について、\(\mathrm{cmax}[c] \leftarrow 0\)とする。

正整数 \(X\) の降順に以下を行う:

1. まず、\(A[r_i][c_i] = X\) を満たすすべての \(i\) について、 \(\mathrm{dp}[i] \leftarrow \max(\mathrm{rmax}[r_i], \mathrm{cmax}[c_i])\) とする。
2. その後、\(A[r_i][c_i] = X\) を満たすすべての \(i\) について、 \(\mathrm{rmax}[r_i] \leftarrow \max(\mathrm{rmax}[r_i], \mathrm{dp}[i] + 1), \mathrm{cmax}[r_i] \leftarrow \max(\mathrm{cmax}[r_i], \mathrm{dp}[i] + 1)\) とする。

以上より、この問題を \(O(N\log N + H + W)\) 時間で解くことができます。
以下に C++言語による実装例を記載します。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int h, w, n;
int r[200005], c[200005], a[200005];
int rmax[200005], cmax[200005];
int dp[200005];
map<int, vector<int> > mp;

int main(void)
{
  cin >> h >> w >> n;
  for(int i = 1; i <= n; i++){
    cin >> r[i] >> c[i] >> a[i];
    mp[a[i]].push_back(i);
  }

  for(auto it = mp.rbegin(); it != mp.rend(); it++){
    for(auto i : it->second) dp[i] = max(rmax[r[i]], cmax[c[i]]);
    for(auto i : it->second){
      rmax[r[i]] = max(rmax[r[i]], dp[i] + 1);
      cmax[c[i]] = max(cmax[c[i]], dp[i] + 1);
    }
  }

  for(int i = 1; i <= n; i++) cout << dp[i] << endl;

  return 0;
}