poj2386 Lake Counting(简单DFS)
推荐:POJ2386 Lake Counting 【DFS】
Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20782 Accepted: 10473 Description Due to recent rains, water has pooled i
2019阿里云双12.12最低价产品入口(新老用户均可),
地址:https://www.aliyun.com/minisite/goods
转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents
题目链接:http://poj.org/problem?id=1562
Description
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.推荐:PPOJ 2386 Lake Counting(DFS)
题意:有一块N*M的土地,有些地方有水,有些地方很干燥,有水标记为'W',干燥为'.'。八连通的积水被认为是连接在一起的(即两个都在同一个九宫格内),问一共有多
Given a diagram of Farmer John's field, determine how many ponds he has.
Input
* Line 1: Two space-separated integers: N and M* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.
Output
* Line 1: The number of ponds in Farmer John's field.Sample Input
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.
Sample Output
3
代码如下:
#include <iostream> #include <algorithm> using namespace std; #include <cstring> #define TM 100+17 int N, M; char map[TM][TM]; bool vis[TM][TM]; int xx[8]={0,1,1,1,0,-1,-1,-1}; int yy[8]={1,1,0,-1,-1,-1,0,1}; void DFS(int x, int y) { vis[x][y] = true; for(int i = 0; i < 8; i++) { int dx = x+xx[i]; int dy = y+yy[i]; if(dx>=0&&dx<N&&dy>=0&&dy<M&&!vis[dx][dy]&&map[dx][dy] == 'W') { vis[dx][dy] = true; DFS(dx,dy); } } } int main() { int i, j; while(cin>>N>>M) { int count = 0; memset(vis,false,sizeof(vis)); for(i = 0; i< N; i++) { cin>>map[i]; } for(i = 0; i < N; i++) { for(j = 0; j < M; j++) { if(map[i][j] == 'W' && !vis[i][j]) { count++; DFS(i,j); } } } cout<<count<<endl; } return 0; }
推荐:POJ 2386 Lake Counting(dfs or bfs)
Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 24999 Accepted: 12619 Description Due to recent rains, water has pooled in va
相关阅读排行
- 1POJ 1930 Dead Fraction
- 2HDU/HDOJ 2563 统计问题 回溯发DFS
- 3poj 1681 Painter's Problem(高斯消元)
- 4POJ 1027 The Same Game 模拟题
- 5Poj 3494 (dp)
用户评论

游客