Lak3 Counting(POJ No.2386)

Lak3 Counting(POJ No.2386)

问题描述:

有个大小为N*M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。求出园子里总共有多少水洼。

N, M <= 100

输入例：

：

问题分析：

八连通即：上、左上、左，左下，下，右下，右，右上。

这道题可以用深入优先搜索（DFS）的思想。

　　1. 寻找是水洼的点。如果找到，标记此点已经记过。

　　　　循环此点的八连通，如果是水，递归循环

　　2. 寻找的次数即为水洼数。

代码：

# include <iostream>
# include <fstream>using namespace std;int N, M;
char map[100][100];void DFS_Search(int i, int j)
{map[i][j] = '.';//这样搞定八循环的方式非常棒！！！for ( int dx = -1; dx <= 1; dx++){for ( int dy = -1; dy <= 1; dy++){int x = i + dx;int y = j + dy;if ( x >= 0 && x <= N && y >= 0 && y <= M && map[x][y] == 'W')DFS_Search(x, y);}}
}int main()
{int count = 0;
//    ifstream cin("Lake_");cin>>N>>M;for( int i = 0; i < N; i++){for ( int j = 0; j < M; j++){cin>>map[i][j];}}for( int i = 0; i < N; i++){for ( int j = 0; j < M; j++){if ( map[i][j] == 'W' ){count++;DFS_Search(i, j);}}}cout<<count<<endl;return 0;
}

转载于:.html