本文主要是介绍Problem 1177 # 深搜又怎样，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
话说xgqin在考虑这个学期ACM课程考试试题的时候，小A同学在QQ上给xgqin留言，以下是两人的对话内容：
小A：老师 小A：明天考试要考察什么算法啊 xgqin：亲，你这个问题让我怎么回答? 小A：就是考试重点是什么 xgqin：sorry 没有终点 xgqin：重点 小A：深搜要考吗 xgqin：呵呵， 小A：懵逼表情 小A：透露一下呗 xgqin：
(PS: 学好语文很重要，以上两人对话中出现了多个错别字）
既然大家对深搜如此热爱，咱们就来一题呗。以下是你需要解决的问题：
在一个M×N的空间中，堆放着很多堆1×1×1的方块，方块的四周可以平铺其他方块，方块的上方也可以叠放其他方块(一块方块上方叠放的方块数不超过8块）。我们把平铺、叠放在一起的方块看成是一堆。你需要做的是找出在这M×N的空间中总共有多少堆方块以及最大的一堆方块包含的方块数。
输入
有多组测试样例。对每组测试样例：
第一行包含两个整型数M和N（1<= M, N<=100）。 接下来包含M行，每行包含N个字符，其中#号表示当前坐标下无方块，否则为1~9的数字字符C表示当前坐标下有C个方块叠放在一起。
输入M N 均为0时表示输入结束，0 0不作为输入样例。
输出
对每组测试样例，输出在M×N空间中，总共有多少堆方块，以及最大一堆方块包含的方块数。
输入范例
10 10 #1######## 121##2#### #3######## ###3333### ########## ##11111### ####1##### #####23### ####6#1### ########## 6 6 1####4 ##23## ###4## #9#5#9 ###6## 2####3 0 0
输出范例
4 18 7 20
超喜欢深搜的哈哈哈#include<stdio.h>
#define MAX 100
int dir[8][2]={{-1,1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int floor[101][101];
int count;
int max;
int number;
int m;
int n;
void dfs(int x,int y)
{if(floor[x][y]==0){return ;}number=number+floor[x][y];floor[x][y]=0;int i;for(i=0;i<8;i++){if((x+dir[i][0]>0)&&(x+dir[i][0]<=m)&&(y+dir[i][1]>0)&&(y+dir[i][1]<=n)){dfs(x+dir[i][0],y+dir[i][1]);}}
}
int main()
{int i;int j;char c;do{scanf("%d %d",&m,&n);if(m==0&&n==0){break;}count=0;max=0;for(i=1;i<=m;i++){getchar();for(j=1;j<=n;j++){scanf("%c",&c);if(c=='#'){floor[i][j]=0;}else {floor[i][j]=c-'0';}}}for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(floor[i][j]>0){number=0;dfs(i,j);count++;if(number>max){max=number;}}}}printf("%d %d\n",count,max);}while(1);return 0;
}这篇关于Problem 1177 # 深搜又怎样的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
