牛客小白月赛——图像存储（BFS+去重）

本文主要是介绍牛客小白月赛——图像存储（BFS+去重），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

图像存储

这道题是学校训练赛遇到的，困扰了许久，最终在网上找到这一种较为简单且容易实现的。除了这一种解法还有其他的比如二维哈希，这里只讲BFS+去重的方法 ~~其实因为其他的都不会~~
先上链接：图像存储
首先若是不考虑题中的第二个问题，图像中黑块的种类，单单只询问图中的黑块数目。是不是很简单，只需要循环寻找每一个黑点（即数字1）sum++。然后以此为起点跑一遍bfs寻找出所有和这一黑点连在一块的黑点，将其置为0即可（或者用vis[][]保存遍历过的点）。

char arr[N][N];
int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};
for(i=0;i<n;i++)
{for(j=0;j<m;j++){if(arr[i][j]=='1'){sum++;//因为bfs时会将找到的整个图像块置为0，所以不会有重复计数bfs(i,j);}}
}
void bfs(int si,int sj)//用bfs寻找图像块//非完整代码，部分注释不符合代码继续往下看即可
{//因为查找顺序都是基于dx,dy数组，所以存入vector的点的都是以相同的顺序int r,c,row,col,k,Min1=si,Min2=sj;queue <node>q;   q.push({si,sj});arr[si][sj]=0;//因为有将找过的点重置0的操作所以不需要vis数组来进行判断while(!q.empty()){node t=q.front();q.pop();row=t.first, col=t.second;for(k=0;k<4;k++){r=row+dy[k], c=col+dx[k];if(r>=0&&r<n&&c>=0&&c<m&&arr[r][c]=='1'){arr[r][c]='0';q.push({r,c});}}}
}

而这个题目的难点在于问题二：如何判断每次遍历出的图像是否之前已经出现过。

因为我们使用for循环自上而下，自左而右寻找新的黑块，每次寻找到一定会是这个黑块的最上面的点（不一定是最右边的点），并且bfs时是以固定的顺序遍历，比如左、右、上、下，或者其他顺序，总之若是两个相同的黑块尽管在矩阵中的位置不同，遍历时找到各个点的顺序是不会变的。
那么我们储存黑块信息时就可以选择用pair来记录点(pair<int,int>分别代表在矩阵中该点的横纵坐标)，将所有点都用vector来储存，那么vector里面就可以把这个黑块的信息存下。最后再用set存这些vector来实现去重。

typedef pair<int,int>node;
typedef vector<node> G;
set<G> shapes;//用set容器去重，set容器自带对pair的函数比较，若要使用结构体则要重载函数

最后还有一个重要的问题，你可能会发现还有一个巨大的bug，虽然相同的黑块点遍历顺序一样，但点的坐标不一样呀，set去重何从谈起？那么我们把所有的黑块移动到矩阵左上角不就行了吗，相同的黑块若都移动到矩阵左上角不就可以去重了吗。
实现：在bfs时遍历每个点时，记录这个黑块的所有点的行数最小值和列数最小值，然后循环保存有所有点的vector容器，将所有点的row -= minrow，col -= mincol.
最终vector里的黑块就是移动到矩阵左上角的情况。
补充一点：有大佬~~山鸡哥~~指出，并不一定要找minrow与mincol，直接以找到的第一个点的横纵坐标去移动也是可以的，因为是用点集来表示黑块，所以不用担心减成负数，最后的相同的图像肯定会移动到重合的。

完整代码：

#include<set>
#include<queue>
#include<utility>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
#define N 1005
int n,m,ans;
char arr[N][N];
int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};
typedef pair<int,int>node;
typedef vector<node> G;
set<G> shapes;//用set容器去重，set容器自带对pair的函数比较，若要使用结构体则要重载函数void bfs(int si,int sj)//用bfs寻找图像块
{//因为查找顺序都是基于dx,dy数组，所以存入vector的点的都是以相同的顺序int r,c,row,col,k,Min1=si,Min2=sj;queue <node>q;   q.push({si,sj});vector<node>g;	 g.push_back({si,sj});arr[si][sj]=0;//因为有将找过的点重置0的操作所以不需要vis数组来进行判断while(!q.empty()){node t=q.front();q.pop();row=t.first, col=t.second;for(k=0;k<4;k++){r=row+dy[k], c=col+dx[k];if(r>=0&&r<n&&c>=0&&c<m&&arr[r][c]=='1'){arr[r][c]='0';q.push({r,c});g.push_back({r,c});//去重的关键，两个Min，分别存此图像块的最上点和最左点Min1 = min(Min1,r);Min2 = min(Min2,c);}}}//去重操作：将所有点的坐标减去两个最小值，可以理解为将所有图像移动到左上角来进行判重的比较for(k=0;k<g.size();k++){g[k].first  -= Min1;g[k].second -= Min2;}if(!shapes.count(g)){shapes.insert(g);}
}int main()
{int i,j,sum;while(scanf("%d %d",&n,&m)){if(n==0)break;for(i=0;i<n;i++){scanf("%s",arr[i]);	}shapes.clear();//记得清空setsum=0, ans=0;for(i=0;i<n;i++){for(j=0;j<m;j++){if(arr[i][j]=='1'){sum++;//因为bfs时会将找到的整个图像置为0，所有不会有重复计数bfs(i,j);}}}ans=shapes.size();printf("%d %d\n",sum,ans);}return 0;
}