思路：
优先队列+bfs 走过的标记掉。
第一次判断标记仍在前面了结果TLE了。。vis放在判断里，不要仍进队列就过来。
#include <iostream> #include <stdio.h> #include <queue> #include <cstring> using namespace std; int n,m; int mp[1005][1005]; int vis[1005][1005]; long long ans; struct node { int x,y; int res; bool operator < (const node &a) const { return res>a.res; } }; bool judge(int x,int y) { if(x<1||x>n||y<1||y>m||vis[x][y]) return false; return true; } void bfs(node t) { priority_queue<node>q; q.push(t); int cnt=n*m; while(!q.empty()) { t=q.top(); q.pop(); if(vis[t.x][t.y]) { continue; } if(cnt==0) break; cnt--; vis[t.x][t.y]=1; ans+=t.res; int to[4][2]={0,1,0,-1,1,0,-1,0}; for(int i=0;i<4;i++) { node c=t; c.x=t.x+to[i][0]; c.y=t.y+to[i][1]; if(judge(c.x,c.y)) { c.res=mp[t.x][t.y]-mp[c.x][c.y]; if(c.res<0) c.res=-c.res; q.push(c); } } } } int main() { int T; cin>>T; for(int k=1;k<=T;k++) { memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); } ans=0; node t; t.res=0,t.x=1,t.y=1; bfs(t); printf("Case #%d:\n",k); printf("%lld\n",ans); } }
