题解 P1845 【影像之结构化特征_NOI导刊2011提高（12）】
这道题是典型的广搜题，然而我在考试的时候用了深搜。。。于是7个点RE，30分。。。（并不知道为什么啊）
题目描述里有个小bug，就是其实寻找第一个点的时候应该从上到下然后再从左到右，而不是从左到右再从上到下，正确的做法应该是像(1,1);(1,2);(1,3);......(2,1);(2,2);(2,3)......的。
接着是思路，说实在最下面那位大佬的解释我看不懂。。。我们找到一个未被覆盖的边缘点后（开始全部都未覆盖），将它的答案设为1，并覆盖这个点，将其放入广搜队列队头，然后寻找它的上下左右四个点，如果它不超过矩阵边缘并且为边缘点，而且还没被覆盖，那么我们就把这个点放入广搜队列的队尾，将它的答案设为队头的答案+1，然后覆盖这个点（这个很重要，如果不直接在插入队尾时覆盖它的话就会有7个点TLE，只能得到30分）。然后一直搜到无路可走，那么这个边缘图需走的步数便是广搜队列中最后一个点的答案。
关于存储答案，楼下zrz大佬用的是优先队列，因为他觉得“sort可能不太好用”，然而我就用了sort，具体就是每次找到一个边缘图，将答案数+1（我用了ans[0]），然后将当前答案存入这个数组中的第ans[0]个中，用sort排序，最后就可以输出了。
如果看不懂前面的就看看代码解释吧，如果还是看不懂的话，欢迎私信向我提问。
（注：有些变量是原来用来备用的，可能在程序里没用）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
using namespace std;
int n,a[1001][1001],ans1,ans[1000001],pc[1001][1001],p[1001][1001];
//a数组用来存储整个矩阵，pc是用来判重的，p是答案
int x[1000001],y[1000001],head,tail,xx,yy;
int fx[4]={1,-1,0,0};
int fy[4]={0,0,-1,1};
char f;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
p[i][j]=2333333;
cin>>f;
if(f=='1')a[i][j]=1;
if(f=='0')a[i][j]=0;}//输入和初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j]==0)continue;
if(pc[i][j]==1)continue;
head=0;tail=1;x[1]=i;y[1]=j;p[i][j]=1;
while(head<tail)
{
head++;
pc[x[head]][y[head]]=1;
for(int i=0;i<=3;i++)
{
xx=x[head]+fx[i];
yy=y[head]+fy[i];
if(xx<1||yy<1||xx>n||yy>n||pc[xx][yy]==1||a[xx][yy]==0)continue;
tail++;
x[tail]=xx;
y[tail]=yy;
p[xx][yy]=p[x[head]][y[head]]+1;
pc[xx][yy]=1;
}
//广搜
}
ans[0]++;
ans[ans[0]]=p[x[tail]][y[tail]];//记录答案
}
sort(ans+1,ans+(ans[0])+1);
cout<<ans[0]<<endl;
for(int i=1;i<=ans[0];i++)
cout<<ans[i]<<endl;//输出
return 0;
}