- 描述
- 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. - 输入
- * 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. - 输出
- * Line 1: The number of ponds in Farmer John‘s field.
- 样例输入
-
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
- 样例输出
-
3
- 提示
- OUTPUT DETAILS:
There are three ponds: one in the upper left, one in the lower left,and one along the right side.
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 struct obj
8 {
9 int xx,yy;
10 };
11
12 int N,M;
13 char a[102][102];
14 int Count;
15
16 int dx[8]={-1,-1,0,1,1,1,0,-1};//从正上方开始，顺时针旋转的8个方向
17 int dy[8]={0,1,1,1,0,-1,-1,-1};
18 void BFS(int x,int y);//从(x,y)开始广搜
19 void DFS(int x,int y);//从(x,y)开始深搜
20 void DFS2(int x,int y);//从(x,y)开始深搜，递归实现
21
22 int main(int argc, char *argv[])
23 {
24 freopen("1388.in","r",stdin);
25 int i,j;
26 scanf("%d%d",&N,&M);getchar();//吸收回车符
27 for(i=0;i)
28 {
29 gets(a[i]);
30 /*
31 for(j=0;j 32 {
33 a[i][j]=getchar();
34 }
35 getchar();//吸收回车符
36 */
37 }
38
39 Count=0;
40 for(i=0;i)
41 {
42 for(j=0;j)
43 {
44 if(a[i][j]==‘W‘)
45 {
46 BFS(i,j);//从（i，j）开始广搜
47 //DFS(i,j);//从（i，j）开始深搜
48 //{ DFS2(i,j); Count=Count+1;} //递归实现的深搜，从(i,j)开始深搜
49 }
50 }
51 }
52 printf("%d\n",Count);
53 return 0;
54 }
55 void BFS(int x,int y)//从（x,y）开始广搜
56 {
57 queue<struct obj> q;
58 struct obj start,temp;
59 int i,txx,tyy;
60
61 start.xx=x;
62 start.yy=y;
63 q.push(start);
64 a[x][y]=‘.‘;
65 while(!q.empty())
66 {
67 for(i=0;i<8;i++)
68 {
69 txx=q.front().xx+dx[i];
70 tyy=q.front().yy+dy[i];
71 if(txx>=0&&txx=0&&tyy‘W‘)
72 {
73 temp.xx=txx;
74 temp.yy=tyy;
75 a[txx][tyy]=‘.‘;
76 q.push(temp);
77 }
78 }
79 q.pop();
80 }
81 Count++;
82 }
83
84 void DFS(int x,int y)//从(x,y)开始深搜
85 {
86 stack<struct obj> s;
87 struct obj start,temp,temp2;
88 int i,txx,tyy;
89
90 a[x][y]=‘.‘;
91 start.xx=x;
92 start.yy=y;
93 s.push(start);
94 while(!s.empty())
95 {
96 temp=s.top(); s.pop();
97 for(i=0;i<8;i++)
98 {
99 txx=temp.xx+dx[i];
100 tyy=temp.yy+dy[i];
101 if(txx>=0&&txx=0&&tyy‘W‘)
102 {
103 temp2.xx=txx;
104 temp2.yy=tyy;
105 a[txx][tyy]=‘.‘;
106 s.push(temp2);
107 }
108 }
109 }
110 Count++;
111 }
112
113 void DFS2(int x,int y)//从(x,y)开始深搜，递归实现
114 {
115 int i,txx,tyy;
116 a[x][y]=‘.‘;
117 for(i=0;i<8;i++)
118 {
119 txx=x+dx[i];
120 tyy=y+dy[i];
121 if(txx>=0&&txx=0&&tyy‘W‘)
122 {
123 //a[txx][tyy]=‘.‘;
124 DFS2(txx,tyy);
125 }
126 }
127 }
京公网安备 11010802041100号