昨天校内比赛做了一个很有意思的题，体面如图：
题目大概意思是，给出一个俯视图矩阵，矩阵内元素表示当前位置有多少个方块，最后要求输出该立体图形中面的数量。
首先给出一组数据：
3 4
2 1 2 1
1 2 3 2
2 1 2 1
这组数据的正解是34，如果需要更多组测试， 把这个图形掉个头，就好。如图：
具体思路是，分不同的面进行统计：首先使用深搜找到所有联通的顶层快，得出面的数量，之后对于每个面（前，后，左，右）进行遍历，得出“多出来的面”的数量。其中有且仅有“沿着遍历方向，后一个高于前一个，更高的面与上一行的面不连通”可以使得面的数量增加。
show the code
#include<iostream> #include<stdio.h> #include<string> #include<set> #include<queue> #include<stack> #include<string.h> #include<algorithm> #include<vector> using namespace std; const long long MAXN=205; long long mapp[MAXN][MAXN]; long long m,n; long long topp=0; long long addd[MAXN][MAXN][4]; long long checkk[MAXN*MAXN]; void dfs(long long x,long long y) { if(checkk[x*MAXN+y]==2)return; checkk[x*MAXN+y]=2; long long now=mapp[x][y]; if(mapp[x+1][y]==now)dfs(x+1,y); if(mapp[x][y+1]==now)dfs(x,y+1); if(x>=1&&mapp[x-1][y]==now)dfs(x-1,y); if(y>=1&&mapp[x][y-1]==now)dfs(x,y-1); } long long calTop() { for(long long i=0;i<n;++i) { for(long long j=0;j<m;++j) { if(checkk[i*MAXN+j]!=2)topp++,dfs(i,j); } } // cout<<topp<<endl; } void init() { cin>>n>>m; for(long long i=0;i<n;++i) { for(long long j=0;j<m;++j) { cin>>mapp[i][j]; } } } long long right() { long long res=0; for(long long i=0;i<n;++i) { for(long long j=1;j<m;++j) { if(mapp[i][j]>mapp[i][j-1]) { res++; addd[i][j][0]++; if(i>0&&addd[i-1][j][0]==1&&mapp[i-1][j-1]<mapp[i][j]&&mapp[i-1][j]>mapp[i][j-1]) { res--; } } } } return res; } long long left() { long long res=0; for(long long i=0;i<n;++i) { for(long long j=m-2;j>=0;--j) { if(mapp[i][j]>mapp[i][j+1]) { res++; addd[i][j][1]++; if(i>0&&addd[i-1][j][1]==1&&mapp[i-1][j+1]<mapp[i][j]&&mapp[i-1][j]>mapp[i][j+1]) { res--; } } } } return res; } long long top() { long long res=0; for(long long j=0;j<m;++j) { for(long long i=1;i<n;++i) { if(mapp[i][j]>mapp[i-1][j]) { res++; addd[i][j][2]++; if(j>0&&addd[i][j-1][2]==1&&mapp[i-1][j-1]<mapp[i][j]&&mapp[i][j-1]>mapp[i-1][j]) { res--; } } } } return res; } long long bottom() { long long res=0; for(long long j=0;j<m;++j) { for(long long i=n-2;i>=0;--i) { if(mapp[i][j]>mapp[i+1][j]) { res++; addd[i][j][3]++; if(j>0&&addd[i][j-1][3]==1&&mapp[i+1][j-1]<mapp[i][j]&&mapp[i][j-1]>mapp[i+1][j]) { res--; } } } } return res; } int main() { memset(mapp,-1,sizeof(mapp)); memset(addd,0,sizeof(addd)); memset(checkk,0,sizeof(checkk)); cin.sync_with_stdio(false); init(); calTop(); topp+=5; topp+=right(); topp+=left(); topp+=top(); topp+=bottom(); cout<<topp<<endl; return 0; }
最后。学校老服务器性能不行，加一行cin.sync_with_stdio(false);分分钟AC。