图像存储

数字图像是一个由“0”和“1”这两个元素组成的矩阵，除去边角上的元素，每个元素都有上下左右相邻的四个元素。再一个数字图像中，元素“0”代表空白，只有元素“1”所在的位置才有一个黑点。由此，一副黑白的图像得以显现。

为了能在更少的空间里存储更多的图像，一个可行的办法就是每种相同的黑块只保留一个，其他的地方只保留位置，这样便实现了压缩。查看时，只需将保留的黑块拓印到其它的位置，这样就实现了图像的复原。

可见，该技术的关键就是对不同的黑块进行记录。我们把由若干个相邻的“1”构成的区域定义为黑块，规定一个孤立的“1”也是一个黑块，黑块中“1”的个数为黑块的大小，通过上下左右平移可以实现重合并且等大的黑块为同一种黑块。现在你的任务是分别算出一个图像中黑块的个数和种数。

多组输入，最多不超过1000组

首行输入2个整数 n , m（ $1\le n , m \le 10^3$ ）代表图像的尺寸。

接下来输入一个n行m列的01矩阵（0和1之间无空格间隔）

以一行中两个0结束输入

n*m的和小于1e7

#include<bits/stdc++.h> using namespace std; const int dx[]={-1,0,1,0}; const int dy[]={0,1,0,-1}; bool b[1010][1010]; int n,m,cnt,ans; map<unsigned long long,bool> c; unsigned long long has; char st[1010][1010]; void dfs(int x,int y) { if(x<1||x>n||y<1||y>m||b[x][y]||st[x][y]=='0') return; b[x][y]=1; for(int i=0;i<4;i++) { int xx=x+dx[i]; int yy=y+dy[i]; dfs(xx,yy); has=has*131+i; } } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; cnt=0;ans=0; memset(b,0,sizeof(b)); c.clear(); for(int i=1;i<=n;i++) scanf("%s",st[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!b[i][j]&&st[i][j]=='1') { has=0; cnt++; dfs(i,j); if(!c[has]) { c[has]=1; ans++; } } printf("%d %d\n",cnt,ans); } return 0; }

详情