题目描述

blablabla

样例

blablabla

算法1

没有使用距离数组d[N][N],这里只简单使用了一个cnt变量，来记录项目经理变成程序员的次数

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<sstream>
#include<queue>
#include<cstring>

using namespace std;
typedef pair<int,int>PII;

const int N=14;
int g[N][N];

int n,m;

int bfs()
{   
    queue<PII> q;
    for(int i=0;i<n;i++)    
        for(int j=0;j<m;j++)
        {
            if(g[i][j]==2) 
                q.push({i,j});
        }

    int cnt=0;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    while(q.size())
    {
        int len=q.size();
        cnt++;
        while(len--)
        {
            auto t=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int a=t.first+dx[i],b=t.second+dy[i];
                if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]==1)
                {
                    g[a][b]=2;
                    q.push({a,b});
                }
            }
        }
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]==1) return -1;
    return cnt-1;
}

int main(){
    string line;
    while(getline(cin,line))
    {
        int k=0;
        stringstream ssin(line);
        while(ssin>>g[n][k]) k++;
        m=k;
        n++;
    }

    cout<<bfs()<<endl;

    return 0;
}

算法2

用距离数组来记录每个点的改变次数

C++ 代码

#include<iostream>
#include<sstream>
#include<queue>
#include<cstring>

using namespace std;
typedef pair<int,int>PII;

const int N=14;
int g[N][N];
int d[N][N];
int n,m;

int bfs()
{   
    queue<PII> q;
    memset(d,-1,sizeof d);
    for(int i=0;i<n;i++)    
        for(int j=0;j<m;j++)
        {
            if(g[i][j]==2) 
            {
                 q.push({i,j});
                 d[i][j]=0;
            }
        }

    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        // cout<<t.first<<' '<<t.second<<' '<<d[t.first][t.second]<<endl;
        for(int i=0;i<4;i++)
        {

            int a=t.first+dx[i],b=t.second+dy[i];

            if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]==1&&d[a][b]==-1)
            {
                d[a][b]=d[t.first][t.second]+1;
                q.push({a,b});
            }
        }
    }

    int res=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]==1)
            {
                if(d[i][j]==-1) return -1;
                else res=max(res,d[i][j]);
            }
    return res;
}

int main(){
    string line;
    while(getline(cin,line))
    {
        int k=0;
        stringstream ssin(line);
        while(ssin>>g[n][k]) k++;
        m=k;
        n++;
    }

    cout<<bfs()<<endl;

    return 0;
}