?
分析
在dp分类里做的，然而并不会$ O(n^3) $ 的$ dp $，怒写一发搜索。
看起来是$ O(n^4) $，但仔细分析了一下好像还挺靠谱的？
poj挂了，没在poj交，在zoj上交的500ms
P.S. 如果要在poj交还要把多数据改成单数据
?
代码
#include <bits/stdc++.h> using namespace std; const int maxn=250; int A[maxn][maxn],num[maxn*maxn],id[1000005],cnt,ok[maxn][maxn],n; int now[maxn][maxn],ans[maxn][maxn],can[maxn][maxn],vis[maxn][maxn]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0}; struct Node{ int x,y,dis,numm; }; bool in(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=n; } queue<Node> que; void bfs(int x,int y,int dis,int numm){ que.push((Node){x,numm}); while(!que.empty()){ Node a=que.front(); que.pop(); x=a.x; y=a.y; dis=a.dis++; numm=a.numm; for(int i=0;i<4;i++){ int px=x+dx[i],py=y+dy[i]; if(!in(px,py) || vis[px][py] || ok[px][py]) continue; vis[px][py]=1; a.x=px; a.y=py; if(dis< now[px][py]){ans[px][py]=numm;can[px][py]=0;now[px][py]=dis;} if(dis==now[px][py]){can[px][py]++;} que.push(a); } } } int main(){ int t; scanf("%d",&t); while(t--){ cnt=0; memset(id,sizeof(id)); memset(num,sizeof(num)); memset(ok,sizeof(ok)); memset(ans,0,sizeof(ans)); memset(can,sizeof(can)); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&A[i][j]); if(A[i][j]) id[A[i][j]]=++cnt,num[cnt]=A[i][j],ok[i][j]=1; } memset(now,127,sizeof(now)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(!ok[i][j]) continue; vis[i][j]=1; bfs(i,j,1,id[A[i][j]]); memset(vis,sizeof(vis)); } for(int i=1;i<=n;i++){ for(int j=1;j<n;j++){ if(!ok[i][j] && can[i][j]==1) printf("%d ",num[ans[i][j]]); else printf("%d ",A[i][j]); } if(!ok[i][n] && can[i][n]==1) printf("%dn",num[ans[i][n]]); else printf("%dn",A[i][n]); } if(t!=0) puts(""); } return 0; }