首页 > 代码库 > POJ2386-Lake Counting
POJ2386-Lake Counting
有一个大小为N*M的园子，雨后积水。八连通的积水被认为是连接在一起的，求出园子里共有多少水洼（八连通是下图中相对W的*部分）。
* * *
*W*
* * *
分析：从任意的W开始，不停地把邻接的部分用‘.‘代替。1次dfs后与初始的W连接的所有的W都被替换成‘.‘，即这个水洼消失了。因此直到图中不存在W为止，总共进行的dfs次数就是答案了。8个方向共对应了8种状态转移，每个格子作为dfs的参数至多被调用一次，所以复杂度为O(8*N*M) = O(N*M)。
1 #include <iostream> 2 using namespace std; 3 4 5 int N, M; 6 char field[100][100]; 7 8 9 //现在位置10 void dfs(int x, int y)11 {12 //将现在位置替换为.13 field[x][y] = ‘.‘;14 15 //循环遍历8个移动方向16 for (int dx = -1; dx <= 1; dx++)17 {18 for (int dy = -1; dy <= 1; dy++)19 {20 //移动到(nx,ny)位置21 int nx = x + dx, ny = y + dy;22 //判断是否再园子内，并且是否有积水23 if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == ‘W‘)24 dfs(nx, ny);25 }26 }27 28 return;29 }30 31 int main()32 {33 while (cin >> N >> M)34 {35 int res = 0;36 for (int i = 0; i < N; i++)37 {38 for (int j = 0; j < M; j++)39 {40 cin >> field[i][j];41 }42 }43 44 45 for (int i = 0; i < N; i++)46 {47 for (int j = 0; j < M; j++)48 {49 //从有W的地方开始dfs50 if (field[i][j] == ‘W‘)51 {52 dfs(i, j);53 res++;54 }55 }56 }57 cout << res << endl;58 }59 60 return 0;61 }
POJ2386-Lake Counting
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。