高橋君の移動経路を \(1\) つ固定したとき、その経路上の整数がすべて異なるかどうかの判定は、実際にその移動経路をたどることで確認することができます。 その際、例えば平衡二分木などを用いると、新たにたどった整数が今までたどった整数のどれかと一致するかを十分高速に判定できます。

高橋君の移動経路としてあり得るものすべてについて、上記の判定を行えば、本問題を解くことができます。 そこで、あり得る移動経路を全列挙することを考えます。

あり得る移動経路は、右への移動をちょうど \(W-1\) 回と下への移動をちょうど \(H-1\) 回含む移動の列です。 そのような列は再帰関数などを用いて列挙できます。

• 再帰を用いる： 「 \((i, j)\) から \((H, W)\) への経路」は、 \((i, j)\) から右に移動した後「 \((i, j+1)\) から \((H, W)\) への経路」を辿るものと、\((i, j)\) から下に移動した後「 \((i+1, j)\) から \((H, W)\) への経路」を辿るものからなります。

あるいは、右への移動を \(0\) 、下への移動を \(1\) で表すと、 あり得る移動経路は、ちょうど \(W-1\) 個の \(0\) とちょうど \(H-1\) 個の \(1\) を含む、長さ \(H+W-2\) の文字列と \(1\) 対 \(1\) に対応するので、 下記の方法などによってそのような列を列挙しても良いです。

• bit 全探索を用いる： \(0\) から \(2^{H+W-2}-1\) までの整数、すなわち、\(H+W-2\) 桁の \(2\) 進数表示で \(000\ldots 0\) から \(111\ldots 1\) までの整数を for ループなどで列挙し、そのうち \(2\) 進数表示で \(1\) である桁の個数がちょうど \(H-1\) 個のものだけを取り出す。

• C++ 言語の next_permutation 関数などを用いる

以下に、C++ 言語による本問題の正解例を記載します。（ next_permutation を用いる例）

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main(void)
{
  int h, w;
  int a[11][11];
  
  cin >> h >> w;
  for(int y = 1; y <= h; y++) for(int x = 1; x <= w; x++) cin >> a[x][y];
  
  int p[20], l = h+w-2, ans = 0;
  for(int i = 1; i <= l; i++){
    if(i > w-1) p[i] = 1;
    else p[i] = 0;
  }
  
  do{
    int x = 1, y = 1;
    set<int> S; S.insert(a[1][1]);
    for(int i = 1; i <= l; i++){
      if(p[i]) y++;
      else x++;
      S.insert(a[x][y]);
    }
    if(S.size() == l+1) ans++;
  }while(next_permutation(p+1, p+l+1));
  
  cout << ans << endl;
  return 0;
}