阿里笔试 八卦镇

#include <bits/stdc++.h>
using namespace std;

int dir[8][2] = {{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0}};
struct point
{
int x;
int y;
};

int bfs(int n, int m, int x, int y, int** A)
{
if(A[x][y]==0)
return 0;

point p{x,y};
queue<point> q;
q.push(p);
point cur;
int sum = 0;
while(!q.empty())
{
cur = q.front();
q.pop();
sum += A[cur.x][cur.y];
A[cur.x][cur.y] = 0;
for(int i=0; i<8; i++)
{
point next;
next.x = cur.x+dir[i][0];
next.y = cur.y+dir[i][1];
if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&A[next.x][next.y]!=0)
{
q.push(next);
}
}
}

return sum;
}

int main()
{
int n; cin>>n;
int m; cin>>m;

int** A = new int*[n];
for(int i=0; i<n; i++)
{
A[i] = new int[m];
memset(A[i], 0, sizeof(int)*m);
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin>>A[i][j];
}
}

int result[8] = {0};
int k=0;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
int tmp=0;
tmp=bfs(n,m,i,j,A);
if(tmp!=0)
{
result[k++] = tmp;
}
}

sort(result, result+8);

cout << "max: " << result[7] << endl;
cout << "min: " << result[0] << endl;

for(int i=0; i<n; i++)
delete[] A[i];
delete[] A;

return 0;