Lake Counting
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. 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 12W........WW..WWW.....WWW....WW...WW..........WW..........W....W......W...W.W.....WW.W.W.W.....W..W.W......W...W.......W. |
題意：
找出水洼的數(shù)量，所有八連通的看做一個
解：
從任意‘w’開始，把能連接的部分用 ' . '表示，一次dfs之后找出一個水洼，直到所有變成 ‘ . ’ 為止。進行dfs次數(shù)為最終答案。
#include <stdio.h>#include <string.h>#include <iostream>using namespace std;char map[105][105];int n,m;int dis[8][2] = {{0,1},{0,-1},{-1,0},{1,0},{1,1},{1,-1},{-1,-1},{-1,1}};void dfs(int x,int y){ if(x<0 || y<0 || x>=n ||y>=m || map[x][y]=='.') return; map[x][y]='.'; for(int i=0;i<8;i++){ int newx = x+dis[i][0]; int newy= y+dis[i][1]; if(newx>=0 && newx<n && newy>=0 && newy<m && map[newx][newy]=='W') { dfs(newx,newy); } } }int main(){ while(~scanf("%d %d",&n,&m)) { memset(map,0,sizeof(0)); int count=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>map[i][j]; } getchar(); } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(map[i][j]=='W') { dfs(i,j); count++; } } } printf("%d/n",count); } return 0;}
新聞熱點
疑難解答
