（补题）拼图游戏

题目描述

克利切洛夫斯基最近制作了一款拼图游戏，在这个游戏中共有K种不同的拼图，克利切洛夫斯基将他们放置在了一个大小为N∗M的网格中，每个格子放置一个拼图。做完这些以后他就去睡觉了，但半夜有一个小偷潜入了他的房间，打算偷走这个拼图。由于房间太黑，小偷看不清这个拼图的具体尺寸，就从网格的左下角开始偷走了大小为X∗Y的一块网格，其中X和Y是任意指定的值，但不会超过原网格的大小，也就是说1≤X≤N，1≤Y≤M。如果将网格的左下角坐标看成(1,1)，右上角坐标看成(N,M)，那么你可以理解为坐标在(1,1)到(X,Y)这个矩形范围内的拼图都被偷走了。

这个小偷的目的是使偷走的拼图中包含全部K种拼图，这样他就可以通过仿制生产盗版的拼图游戏了。克利切洛夫斯基虽然听到了小偷的声音，但他过于胆小，不敢出去阻止小偷。他只希望聪明的你帮他计算出，小偷有多少种选择X和Y的方案，会使得(1,1)到(X,Y)这个矩形范围内包含全部K种拼图。

输入

多组测试数据，第一行输入一个T表示数据的组数（1≤T≤10）。

每组数据第一行包含三个整数N，M，K，分别表示网格的宽、网格的高以及拼图的种类数量。

每组数据接下来N行，每行M个整数，第i行第j个整数表示坐标在(i,j)这个位置的拼图是哪一种。保证颜色的范围在1到K之间。

输入数据满足(1≤N≤1,000，1≤M≤1,000，1≤K≤2,000)，且多组数据N∗M的总和不超过5,000,000

输出

仅一行一个整数，表示有多少对满足条件的X和Y。

样例输入

复制

23 3 31 1 12 2 23 3 33 3 21 2 12 1 21 2 1

样例输出

复制

38

代码 

#includeusing namespace std;int t,n,m,k,p[1001][1001];int find(int x){int c[2009]{0},t=0;for(int i=0;i<m;++i){for(int j=0;j<=x;++j){if(!c[p[j][i]]){ c[p[j][i]]=1; t++; } if(t==k)return i;}}return m;}int main(){scanf(\"%d\",&t);while(t--){scanf(\"%d%d%d\",&n,&m,&k);for(int i=0;i<n;++i){for(int j=0;j<m;++j)scanf(\"%d\",&p[i][j]);}int ans=0;for(int i=0;i<n;++i){ans+=m-find(i);}printf(\"%d\\n\",ans);}return 0;}