ACM-搜索聪会长的关爱：dfs计算最大八方联通块的面积

本文主要是介绍ACM-搜索聪会长的关爱：dfs计算最大八方联通块的面积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：和紫书162页的油田意思差不多，只是这里不是求联通块的块数，而是找最大块，并计数最大块的面积。

输入：多组输入。每组第一行输入两个数m和n (n,m范围0~1000)，表示教室的大小，有m行n列的座位。当m和n为0时停止程序。输入一个教室的人员分布图，用一个矩阵表示，其中“@”表示小姐姐，“*”表示丑陋的男人。

5 5
****@
*@@*@
*@**@
@@@*@
@@**@
4 4
****
*@@*
*@**
****
2 8
*@@@@@@@
*****@@@
0 0

输出：每组输出一行一个数字，表示聪聪最多能撩到的小姐姐数量。

8
3
10

太……久没写搜索，我都不会写了，之前写了一个，但是一直出现意外错误，好想哭……
思路：这里就是暴力一个个搜过去，我的思路有以下几个注意：
1.八方处理：用fx[8],fy[8]匹配来试探八个方向的可能性。
2.没有用vis[1005][1005,而是直接在map上面修改地图，即搜过的点@直接换成*，这样可以避免重复搜，陷入死循。
3.一开始写错就是因为判断条件的位置放错了，用成了回溯的板子…..而且没注意好枚举八方时的dfs调用判断。

错误代码如下！！！！不要抄，知道是错的就好

//八个方向遍历，会有反复进行相互遍历的取向，会死循 
void dfs(int x,int y){if(end(x,y))return;//结束判断 else for(int i=0;i<8;i++){int xx=x+fx[i],yy=y+fy[i]; if(map[xx][yy]=='@'){map[xx][yy]=='*';dfs(xx,yy);}}
}

1.预处理，分配空间

int m,n,i,j;
int fx[8]= {-1,1,0,0,1,-1,-1,1};
int fy[8]= {0,0,-1,1,-1,-1,1,1};
char map[1005][1005];

2.重点！！！dfs

int dfs(int x,int y){//if(x<0||x>=n||y<0||y>=m)return 0;//结束判断 //if(map[x][y]!='@')return 0;//结束判断//处理 map[x][y]='*';int sum=1;for(int i=0;i<8;i++){int xx=x+fx[i],yy=y+fy[i];if(map[xx][yy]=='@'&&xx<n&&xx>=0&&yy<m&&yy>=0){//即进入dfs的位置一定是可行的@//vis[xx][yy]=1;sum+=dfs(xx,yy);}}return sum;
}

3.主函数调用处理最大值更新

int main()
{//freopen("3.txt","r",stdin);while(cin>>n>>m&&n&&m)//n行m列 {for(i=0;i<n;i++){scanf("%s",map[i]);}int cnt=0;for(i=0;i<n;i++){for(j=0;j<m;j++){if(map[i][j]=='@'){ cnt=max(cnt,dfs(i,j));//更新最大面积}       }}cout<<cnt<<endl;}return 0;
}