[2021] Tencent autumn recruitment technology post programming arrangement supermarket

  Their thinking ： Maze problems , Determine how many connected blocks contain the house . Select a point inside the connecting block to build a supermarket , Make the distance shortest .bfs Determine connected block ,bfsC Used to calculate the distance to build a supermarket at a certain point .

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,v[55][55],cnt,sum;
int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
char a[55][55];
int bfsC(int xx,int yy) /**<  Used to calculate in xx,yy When building a supermarket , The distance from other houses to this supermarket , Note that you must search , You can't find the Manhattan distance directly  */
{
    int i,j,x,y,qx[3000],qy[3000],f=0,r=0,v[55][55]={0},dis=0;/**<  This v Will mask the global v Array  */
    qx[r]=xx,qy[r++]=yy;
    v[xx][yy]=1;
    while(f<r)
    {
        x=qx[f],y=qy[f++];
        if(a[x][y]=='#')
            dis+=v[x][y]-1;;
        for(i=0; i<4; i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]!='*'&&v[nx][ny]==0)
            {
                v[nx][ny]=v[x][y]+1;/**<  Record the distance  */
                qx[r]=nx,qy[r++]=ny;
            }
        }
    }
    return dis;
}
void bfs(int x,int y)
{/**< qx,qy Handwriting queue , Share a head and tail pointer  */
    int i,j,qx[3000],qy[3000],f=0,r=0,minDis=9999999;
    int house[2505][2],num=0;
    qx[r]=x,qy[r++]=y;
    v[x][y]=1;
    while(f<r)
    {
        x=qx[f],y=qy[f++];
        if(a[x][y]=='#') /**<  Save the house , Used to calculate  */
            house[++num][0]=x,house[num][1]=y;
        for(i=0; i<4; i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]!='*'&&v[nx][ny]==0)
            {
                v[nx][ny]=1;
                qx[r]=nx,qy[r++]=ny;
            }
        }
    }
    if(num>0)/**<  Need to build a supermarket  */
        cnt++;
    for(i=0; i<r; i++) /**<  Write a line on it qx,qy Inside , The element values are still  */  /**<  Check on (qx[i],qy[i]) The total distance to build a supermarket , Write another deep search or wide search to do this  */
        minDis=min(minDis,bfsC(qx[i],qy[i]));
    sum+=minDis;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1; i<=n; i++) 
        cin>>a[i]+1;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(a[i][j]!='*'&&v[i][j]==0)
                bfs(i,j);/**<  A new connected block  */
    cout<<cnt<<' '<<sum;
    return 0;
}