题解：
如果没有相同数字，那么我们把每行按数值从小到大连边，每列按数值从小到大连边，边权为1，然后拓扑序DP一下，每个点的值就是最长路的长度
现在有相同数字，怎么处理？
考虑我们同一行同一列的相同数字连双向边（不需要两两连边，只需要使其连通就行），边权为0
然后我们的图就变成了一个类似DAG但是里面有一堆边权为0并由双向边的连通块组成的东西。
那么我们考虑缩点，缩掉边权为0的边，然后就是个DAG，拓扑序DP一下就好了。
1 #include<bits/stdc++.h> 2 #define pii pair<int,int> 3 #define mp(a,b) make_pair(a,b) 4 #define maxn 1000005 5 using namespace std; 6 int n,m; 7 vector<vector<int>> a; 8 vector<pii> b; 9 struct edge 10 { 11 int to,next,w; 12 }e[maxn<<2]; 13 int head[maxn<<1],p; 14 void addedge(int u,int v,int w) 15 { 16 e[++p].to=v;e[p].w=w;e[p].next=head[u];head[u]=p; 17 } 18 int id(int x,int y) 19 { 20 return (x-1)*m+y; 21 } 22 int cnt; 23 bool vis[maxn]; 24 int dis[maxn<<1],d[maxn<<1]; 25 vector<int> s[maxn<<1]; 26 int belong[maxn]; 27 void dfs(int u,int x) 28 { 29 s[x].push_back(u); 30 for(int i=head[u];i;i=e[i].next)if(!e[i].w) 31 { 32 int v=e[i].to; 33 if(!vis[v])vis[v]=1,dfs(v,x); 34 } 35 } 36 void toposort() 37 { 38 queue<int> q; 39 for(int i=1;i<=p;++i)if(e[i].w!=-1)d[e[i].to]++; 40 for(int i=1;i<=cnt;++i)if(!d[i])q.push(i),dis[i]=1; 41 while(!q.empty()) 42 { 43 int u=q.front();q.pop(); 44 for(int i=head[u];i;i=e[i].next)if(e[i].w!=-1) 45 { 46 int v=e[i].to; 47 dis[v]=max(dis[v],dis[u]+e[i].w); 48 d[v]--; 49 if(!d[v])q.push(v); 50 } 51 } 52 } 53 int main() 54 { 55 scanf("%d%d",&n,&m); 56 cnt=n*m; 57 vector<int> T; 58 T.clear();a.push_back(T); 59 for(int i=1;i<=n;++i) 60 { 61 T.clear(); 62 T.push_back(0); 63 for(int j=1;j<=m;++j) 64 { 65 int x;scanf("%d",&x); 66 T.push_back(x); 67 } 68 a.push_back(T); 69 } 70 for(int i=1;i<=n;++i) 71 { 72 b.clear(); 73 for(int j=1;j<=m;++j)b.push_back(mp(a[i][j],j)); 74 sort(b.begin(),b.end()); 75 for(int j=1;j<b.size();++j) 76 { 77 int u=id(i,b[j].second),v=id(i,b[j-1].second); 78 if(b[j].first==b[j-1].first)addedge(v,u,0),addedge(u,v,0); 79 else addedge(v,u,1); 80 } 81 } 82 for(int j=1;j<=m;++j) 83 { 84 b.clear(); 85 for(int i=1;i<=n;++i)b.push_back(mp(a[i][j],i)); 86 sort(b.begin(),b.end()); 87 for(int i=1;i<b.size();++i) 88 { 89 int u=id(b[i].second,j),v=id(b[i-1].second,j); 90 if(b[i].first==b[i-1].first)addedge(v,u,0),addedge(u,v,0); 91 else addedge(v,u,1); 92 } 93 } 94 for(int i=1;i<=n*m;++i)if(!vis[i]) 95 { 96 dfs(i,++cnt); 97 for(int j=0;j<s[cnt].size();++j) 98 { 99 int u=s[cnt][j]; 100 belong[u]=cnt; 101 } 102 } 103 p=0; 104 memset(head,0,sizeof(head)); 105 for(int i=1;i<=n;++i) 106 { 107 b.clear(); 108 for(int j=1;j<=m;++j)b.push_back(mp(a[i][j],j)); 109 sort(b.begin(),b.end()); 110 for(int j=1;j<b.size();++j) 111 { 112 int u=id(i,b[j].second),v=id(i,b[j-1].second); 113 u=belong[u],v=belong[v]; 114 if(b[j].first!=b[j-1].first)addedge(v,u,1); 115 } 116 } 117 for(int j=1;j<=m;++j) 118 { 119 b.clear(); 120 for(int i=1;i<=n;++i)b.push_back(mp(a[i][j],i)); 121 sort(b.begin(),b.end()); 122 for(int i=1;i<b.size();++i) 123 { 124 int u=id(b[i].second,j),v=id(b[i-1].second,j); 125 u=belong[u];v=belong[v]; 126 if(b[i].first!=b[i-1].first)addedge(v,u,1); 127 } 128 } 129 toposort(); 130 for(int i=n*m+1;i<=cnt;++i) 131 { 132 for(int j=0;j<s[i].size();++j) 133 { 134 int u=s[i][j]; 135 dis[u]=dis[i]; 136 } 137 } 138 int tot=0; 139 for(int i=1;i<=n;++i) 140 { 141 for(int j=1;j<=m;++j)printf("%d ",dis[++tot]); 142 puts(""); 143 } 144 return 0; 145 }