BoundingBox

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains two integers n and m -- the size of the matrix.

The second line contains $n \cdot m$ integers $a_{1,1}, a_{1,2}, \ldots, a_{1, m}$ , $a_{2,1}, a_{2,2}, \ldots, a_{2, m}$ , $\ldots$ , $a_{n, 1}, a_{n, 2}, \ldots, a_{n,m}$ , where $a_{i,j}$ is the value in the i-th row and the j-th column.

* $1 \leq n \cdot m \leq 10^6$
* $1 \leq a_{i,j} \leq nm$
* It is guaranteed that all cells which contain the same value are 4-side connected.
* It is guaranteed that the sum of $n \cdot m$ in all test cases does not exceed $10^7$ .

C++(clang++11) 解法, 执行用时: 3205ms, 内存消耗: 148968K, 提交时间: 2020-10-31 16:39:03

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
const int N=1001000;
ll ret,ans;
int a[N],le[N],vis[N],cnt,ri[N],up[N],dw[N],n,m;
inline int id(int x,int y){return (x-1)*m+y;}
vector<int>g[N];
bool in_test(int x,int y){return le[y]<=le[x]&&ri[x]<=ri[y]&&up[y]<=up[x]&&dw[x]<=dw[y];}
bool li_test(int x,int y){return ri[x]<le[y]||ri[y]<le[x]||dw[x]<up[y]||dw[y]<up[x];}
void add(int x,int y){
	y=a[y];if(x==y)return;
	if(in_test(x,y)||in_test(y,x)||li_test(x,y))return;
	g[x].push_back(y);g[y].push_back(x);
}
void chk(int x,int y){
	if(x==y||vis[y]==cnt)return;
	vis[y]=cnt;
	ret+=y;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	for(;cin>>n>>m;){
		for(int i=1;i<=n*m;++i)
			le[i]=n+1,ri[i]=0,up[i]=m+1,dw[i]=0,g[i].clear();
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j){
				int x;cin>>x;a[id(i,j)]=x;
				le[x]=min(le[x],i);ri[x]=max(ri[x],i);
				up[x]=min(up[x],j);dw[x]=max(dw[x],j);
			}
		ans=0;
		for(int i=1;i<=n*m;++i)
			if(le[i]<=ri[i]&&up[i]<=dw[i]){
				int L=ri[i]-le[i]+1,R=dw[i]-up[i]+1;
				for(int j=max(1,le[i]-L);j<=min(n,ri[i]+L);++j)
					add(i,id(j,up[i])),
					add(i,id(j,dw[i]));
				for(int j=max(1,up[i]-R);j<=min(m,dw[i]+R);++j)
					add(i,id(le[i],j)),
					add(i,id(ri[i],j));
			}
		for(int i=1;i<=n*m;++i)if(le[i]<=ri[i]&&up[i]<=dw[i]){
			++cnt;ret=0;
			for(int j:g[i])chk(i,j);
			ans+=ret^i;
		}
		cout<<ans<<'\n';
	}

	return 0;
}

详情