poj 2386 DFS搜索基础
最初不会的地方：
1、 其实连样例开始的时候就没读懂……
2、 从哪里搜？
3、 搜的边界？
4、 把一片搜完了，然后呢？
5、 回溯吗？（这道题看到了回溯和DFS的区别）
标程的解决方法：
2、任何一个位置都可以，反复搜，所以从（0，0）位置起
3、搜的结果是把可以连为一片的W都标为1，W周围的.仍作为边界。
4、搜到所有的W都标为1的时候 搜索就结束了。（其实有这个原因：每个W必然属于一个区域，ans至少一个区域，当还有w没有被标记，就说明还有区域计数，当所有的W都被计数，就可以输出Ans）
另外，此题还然我学到几点：
一、int dir[2][8]={{-1,-1,-1,0,0,1,1,1},{-1,0,1,-1,1,-1,0,1}};
左边的{}是行坐标，右边是列坐标。
这样dfs的时候就不用写八个了……
void dfs(int i,int j)
{
int k,a,b;
for(k=0;k<8;k++)
{
a=dir[0][k]+i;
b=dir[1][k]+j;
if(a>=0&&a<=n&&b>=0&&b<=m&&!vis[a][b]&&map[a][b])
{
vis[a][b]=1;
dfs(a,b);
}
}
}
二读入map直接记录为1，0
三、好好看本题的代码，体会回溯和DFs区别
贴代码：
Lake Counting
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 16081
Accepted: 8141
Description
Due to recentrains, water has pooled in various places in Farmer John's field, which isrepresented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100)squares. Each square contains either water ('W') or dry land ('.'). Farmer Johnwould like to figure out how many ponds have formed in his field. A pond is aconnected set of squares with water in them, where a square is consideredadjacent to all eight of its neighbors.
Given a diagram of Farmer John's field, determine how many ponds he has.
Input
* Line 1: Twospace-separated integers: N and M
* Lines 2..N+1: M characters per line representing one row of Farmer John'sfield. Each character is either 'W' or '.'. The characters do not have spacesbetween them.
Output
* Line 1: Thenumber 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
Hint
OUTPUTDETAILS:
There are three ponds: one in the upper left, one in the lower left,and onealong the right side.
Source
USACO2004 November
#include<cstdio>#include<cstring>using namespace std;#define N 101bool vis[N][N],map[N][N];int fi,fj,m,n,count;int dir[2][8]={{-1,-1,-1,0,0,1,1,1},{-1,0,1,-1,1,-1,0,1}};int find(){ int i,j; for(i=0;i<n;i++) for(j=0;j<m;j++) { if(!vis[i][j]&&map[i][j]) { fi=i; fj=j; return 1; } } return 0;}void dfs(int i,int j){ int k,a,b; for(k=0;k<8;k++) { a=dir[0][k]+i; b=dir[1][k]+j; if(a>=0&&a<=n&&b>=0&&b<=m&&!vis[a][b]&&map[a][b]) { vis[a][b]=1; dfs(a,b); } }}int main(){ int i,j; char c; while(scanf("%d%d",&n,&m)!=EOF) { memset(vis,0,sizeof(vis)); memset(map,0,sizeof(map)); count=0; for(i=0;i<n;i++) for(j=0;j<m;j++) { scanf("%c",&c); if(c=='W')map[i][j]=1; else if(c=='.')map[i][j]=0; else if(c==' '||c=='\n'||c=='\0')j--; } while(find()) { vis[fi][fj]=1; dfs(fi,fj); count++; } printf("%d\n",count); } return 0;}