N*M的园子,雨后积起了水.八连通的积水背认为是连接在一起的.请求出园子里总共有多少水洼?
dfs(Depth-First Search) 八个方向的简单搜索....
深度优先搜索从最开始的状态出发,遍历所有可以到达的状态.由此可以对所有的状态进行操作,或者列举出所有的状态.
int N,M;
char field[][]; void dfs(int x,int y)
{
field[x][y]=='.'; //将现在所在位置替换
for(int dx=-; dx<=; dx++){
for(int dy=-; dy<=; dy++){ //向x方向移动dx,向y方向移动dy,移动的结果为(nx,ny)
int nx=x+dx;
int ny=y+dy;
if(<=nx && nx<N && <ny && ny<M && field[nx][ny]=='W') //判断(nx,ny)是不是在园子内,以及是否有积水
dfs(nx,ny);
}
}
} void solve(){
int ans=;
for(int i=; i<N; i++){
for(int j=; j<M; j++){
if(field[i][j]=='W'){ //从有W的地方开始dfs
dfs(i,j);
ans++;
}
}
}
printf("%d\n",ans);
}