When a path is fixed, one can determine if the integers on the path are distinct by actually traversing the path. Here, one can use a balanced binary tree for example to determine fast enough if each integer coincides with those visited so far.

One can solve the problem by checking as described above for all the possible Takahashi’s paths. Now we consider how to enumerate all the possible paths.

A possible path is a sequence of moves that contains exactly \((W-1)\) moves to the left and \((H-1)\) moves to the down. Such a sequence can be enumerated with a recursive function.

• Using a recursive function: “a path from \((i, j)\) to \((H, W)\)” consists of those starting with a move to the left from \((i, j)\), succeeded by paths from \((i, j+1)\) to \((H, W)\), and those starting with a move to the down from \((i, j)\), succeeded by paths from \((i+1, j)\) to \((H, W)\).

Alternatively, when the move to the left is denoted by \(0\) and down by \(1\), each possible path corresponds one-by-one to a string of length \((H+W-2)\) consisting of exactly \((W-1)\) \(0\)s and exactly \((H-1)\) \(1\)s, so one can enumerate such sequences by, for example:

• using bit burteforcing: enumerate integers between \(0\) and \(2^{H+W-2}-1\), i.e. \((H+W-2)\)-digit integers from \(000\ldots 0\) through \(111\ldots 1\) base \(2\), with a for loop, and then take those which has \((H-1)\) ones in the base-two representation.

• use the function next_permutation

The following is a sample code in C++ language (using 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;
}