\(A\) が \(0\) を含まない場合

まず、簡単のために、\(A\) に \(0\) が含まれない場合を考えます。

\(A\) が問題文中の条件

\[A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H-1, W} \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}\]

を満たすことは、\(A\) が下記の \(2\) つの条件をともに満たすことと同値です。

1. \(i\) 行目の最小値を \(m_i\) 、最大値を \(M_i\) として、 \(m_1 \leq M_1 \leq m_2 \leq M_2 \leq m_3 \leq \cdots \leq m_H \leq M_H\)

2. すべての \(j = 1, 2, \ldots, W-1\) について、次が成り立つ。

   • すべての行 \(i\) について、\(A_{i, j} \leq A_{i, j+1}\)

行の入れ替えの操作と列の入れ替えの操作は可換です。 また、列の入れ替えを行っても「上記条件 1. を満たすかどうか」は変わりません。 同様に、行の入れ替えを行っても「上記条件 2. を満たすかどうか」は変わりません。 したがって本問題は、

• 行の入れ替えを好きなだけ行って、条件 1. を満たすようにできるかという行の並べ替え問題と
• 列の入れ替えを好きなだけ行って、条件 2. を満たすようにできるかという列の並べ替え問題

の \(2\) つの独立な問題に分けられます。

・行の並べ替え問題

• まず、各行における要素の最小値と最大値の組 \((m, M)\) を求めます。
• 次に、\(H\) 個の行を、\(m\) の昇順に（ \(m\) が等しいものどうしはさらに \(M\) の昇順に）並べ替えます。
• そして、得られた \(A\) が、条件 1. を満たすかを判定すれば良いです。

・列の並べ替え問題

\(W\) 個の列に対応する \(W\) 個の頂点を持ち、すべての行 \(i\) について次の手順（★）を行って得られる有向グラフ \(G\) を考えます。

（★） \(A_{i, j} \lt A_{i, j'}\) を満たすすべての組 \((j, j')\) について、頂点 \(j\) から頂点 \(j'\) に有向辺を張る。

つまり、最終的に条件 2. を達成する上で、

「初期状態で \(j\) 番目にある列」が、「初期状態で \(j'\) 番目にある列」よりも、最終的な \(A\) においてより左になければならない

という制約があるとき、かつ、そのときに限り、頂点 \(j\) から頂点 \(j'\) への有向辺を張ったグラフです。 条件 2. を満たすように列を並べ替えられることは、この有向グラフ \(G\) のトポロジカル順序が存在することと同値であるため、\(G\) が DAG かどうかを判定すればこの問題が解けます。

しかし、上のグラフ \(G\) は非常に多くの辺を含む場合があり、実行制限時間に間に合わせることは絶望的です。 そこで、上の \(G\) と等価で頂点数・辺数が十分少ない有向グラフ \(G'\) を構築します。具体的には、\(G\) の構築において上記の（★）を下記の手順で置き換えて得られるグラフを構築します。

\(i\) 行目を昇順にソートしたものを

\[A_{i, j_{1, 1}} = A_{i, j_{1, 2}} = \cdots = A_{i, j_{1, l_1}} \lt A_{i, j_{2, 1}} = A_{i, j_{2, 2}} = \cdots = A_{i, j_{2, l_2}} \lt \cdots \lt A_{i, j_{k, 1}} = A_{i, j_{k, 2}} = \cdots = A_{i, j_{k, l_k}} \]

とする。新たに \(k-1\) 個の頂点 \(v_{i, 1}, v_{i, 2}, \ldots, v_{i, k-1}\) グラフに追加し、下記の通りに有向辺を張る。

• \(l_1\) 個の頂点 \(j_{1, 1}, j_{1, 2}, \ldots, j_{1, l_1}\) それぞれから頂点 \(v_{i, 1}\) への有向辺、および、頂点 \(v_{i, 1}\) から \(l_2\) 個の頂点 \(j_{2, 1}, j_{2, 2}, \ldots, j_{2, l_2}\) それぞれへの有向辺を張る。
• \(l_2\) 個の頂点 \(j_{2, 1}, j_{2, 2}, \ldots, j_{2, l_2}\) それぞれから頂点 \(v_{i, 2}\) への有向辺、および、頂点 \(v_{i, 2}\) から \(l_3\) 個の頂点 \(j_{3, 1}, j_{3, 2}, \ldots, j_{3, l_3}\) それぞれへの有向辺を張る。
• \(\cdots\)
• \(l_{k-1}\) 個の頂点 \(j_{k-1, 1}, j_{k-1, 2}, \ldots, j_{k-1, l_{k-1}}\) それぞれから頂点 \(v_{i, k-1}\) への有向辺、および、頂点 \(v_{i, k-1}\) から \(l_k\) 個の頂点 \(j_{k, 1}, j_{k, 2}, \ldots, j_{k, l_k}\) それぞれへの有向辺を張る。

このグラフ \(G'\) の頂点数と辺数は \(O(HW)\) であるため、実行制限時間に間に合わせることができます。

\(A\) が \(0\) を含む場合

最後に、\(A\) が \(0\) を含む場合について述べます。 問題文中の順番とは逆に、まず行や列の入れ替えの操作を好きなだけ行ってから最後にすべての \(0\) を正の整数に置き換えるとしても良いです。

列 \(A' \coloneqq (A_{1, 1}, A_{1, 2} , \ldots, A_{1, W}, A_{2, 1} , A_{2, 2}, \ldots, A_{2, W}, A_{3, 1}, \ldots, A_{H-1, W}, A_{H, 1}, A_{H, 2}, \ldots, A_{H, W})\) からすべての \(0\) を取り除いて得られる部分列が広義単調増加であれば、\(A'\) に含まれるそれぞれの \(0\) を適切な正の整数で置き換えることで、\(A'\) を広義単調増加にすることができます。

例えば、\(A' = (0, 0, 2, 0, 3, 4, 0, 0, 4, 0, 5, 0)\) であれば、 \(A' = (\red{1}, \red{1}, 2, \red{2}, 3, 4, \red{4}, \red{4}, 4, \red{4}, 5, 5, \red{5})\) とすれば良いです。

したがって、\(A\) の要素のうち \(0\) であるものは無視するという条件下で、\(A\) が \(0\) を含まない場合と同様に解けばよいです。

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

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

int h, w;
int a[1000005];
vector<int> G[2000005];
bool used[2000005];
vector<int> topo;

void dfs(int v)
{
  used[v] = true;
  for(auto u : G[v]) if(!used[u]) dfs(u);
  topo.push_back(v);
}

int main(void)
{
  cin >> h >> w;
  for(int y = 1; y <= h; y++) for(int x = 1; x <= w; x++) cin >> a[(y-1)*w+(x-1)];
  
  vector<pair<int,int>> vec;
  for(int y = 1; y <= h; y++){
    int l = 1e9, r = -1e9;
    for(int x = 1; x <= w; x++){
      int v = a[(y-1)*w+(x-1)];
      if(v) l = min(l, v), r = max(r, v);
    }
    if(l <= r) vec.push_back({l, r});
  }
  sort(vec.begin(), vec.end());
  
  for(int i = 1; i < (int)vec.size(); i++){
    if(vec[i-1].second > vec[i].first){
      cout << "No"<< endl;
      return 0;
    }
  }
  
  for(int y = 1; y <= h; y++){
    vector<pair<int, int>> vec;
    for(int x = 1; x <= w; x++) if(a[(y-1)*w+(x-1)]) vec.push_back({a[(y-1)*w+(x-1)], x});
    sort(vec.begin(), vec.end());
    
    for(int i = 1; i < (int)vec.size(); i++){
      if(vec[i-1].first != vec[i].first){
        int v = w + vec[i-1].first;
        for(int j = i-1; j >= 0; j--){
          if(vec[j].first != vec[i-1].first) break;
          G[vec[j].second].push_back(v);
        }
        for(int j = i; j < (int)vec.size(); j++){
          if(vec[j].first != vec[i].first) break;
          G[v].push_back(vec[j].second);
        }
      }
    }
  }
  
  int n = w + h*w;
  for(int i = 1; i <= n; i++) if(!used[i]) dfs(i);
  reverse(topo.begin(), topo.end());
  
  for(int i = 1; i <= n; i++) used[i] = false;
  for(auto v : topo){
    used[v] = true;
    for(auto u : G[v]){
      if(used[u]){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;

  return 0;
}