自动搬运

查看原文

来自洛谷，原作者为

	AFOier **

搬运于2025-08-24 21:31:00，当前版本为作者最后更新于2017-08-25 16:55:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题是典型的广搜题，然而我在考试的时候用了深搜。。。于是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;
}