学步园

觉得有点像并查集啦。

以前的DFS水题都是搜的四个方向，现在搜八个了。。。FT。。

感觉这个不是太像DFS。。。没有回溯塞。。。觉得就是递归。。。额。。

@的八个方向有@的并一起，输出有多少个。。额。。多少棵这样的树吧，恩，可以这么说。

#include<stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <memory.h><br /> using namespace std;<br /> int map[110][110];<br /> int visit[110][110];<br /> int m,n,cou;<br /> int dir[16] = { 1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1};<br /> int fi,fj;<br /> int find()<br /> {<br /> for(int i=1; i<=m; i++)<br /> for(int k=1; k<=n; k++)<br /> {<br /> if(!visit[i][k] && map[i][k])<br /> {<br /> fi = i;<br /> fj = k;<br /> return 1;<br /> }<br /> }<br /> return 0;<br /> }<br /> void DFS(int i , int j )<br /> {<br /> visit[i][j] = 1;<br /> for(int k=0; k<16; k+=2)<br /> {<br /> int a = i+dir[k];<br /> int b = j+dir[k+1];<br /> if( a>=1 && a<=m && b>=1 && b<=n && map[a][b] && !visit[a][b] )<br /> {<br /> visit[a][b] = 1;<br /> DFS(a,b);<br /> }<br /> }<br /> }<br /> int main(void)<br /> {<br /> char str[110];<br /> while( cin >> m >> n && m )<br /> {<br /> cou = 0;<br /> memset(visit,0,sizeof(visit));<br /> for(int i=1; i<=m ;i++)<br /> {<br /> cin >> str;<br /> for(int k=0; k<n; k++)<br /> map[i][k+1] = (str[k] == '*'? 0 : 1);<br /> }<br /> while( find() )<br /> {<br /> cou++;<br /> DFS(fi,fj);<br /> }<br /> cout << cou << endl;<br /> }<br /> return 0;<br /> }<br />