题目链接：HDU 1241
题意：
给一个二维字符数组，‘@’代表有油，‘*’代表没有，如果两个油田在水平或竖直或对角线方向相通，那么这两个油田属于同一个pocket，pocket里可能也只有一个油田。问给定的油藏情况共有多少个pocket？
分析：
两天前做的时候还没有头绪，今天拿出来又想了一下，突然有了思路。
同样是BFS搜索。但是每次搜索是从一个尚未被访问的油田开始，然后把从这个油田开始可以连通的所有油田都标记上，也就是搜索这一个pocket里的所有油田。那么在下一次搜索时一定是另一个pocket了。这样一来，有多少次BFS就有多少个pocket了。想通了这一点就很简单了。
注意点：
- 搜索方向有八个，不是4个，也不是6个。
- 标记一定要进队列之前标记，而不是出队列时标记，否则会Memory Limit Exceeded.
CODE:
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;const int maxn = 110;
int dir[8][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } ,{-1,-1},{1,1} ,{-1,1},{1,-1} };
int a[maxn][maxn], vis[maxn][maxn], ans, m, n;
char s[maxn];int valid(int x, int y)
{if (x < 0 || y < 0 || x >= m || y >= n || vis[x][y] || a[x][y]==0) return 0;return 1;
}
struct Node {int x, y;
}cur, nextnode;void bfs(int w, int r)
{ans++;queue<Node> q;cur.x = w;cur.y = r;vis[cur.x][cur.y] = 1;q.push(cur);while (!q.empty()){cur = q.front();q.pop();for (int i = 0;i < 8;i++){nextnode.x = cur.x + dir[i][0];nextnode.y = cur.y + dir[i][1];if (!valid(nextnode.x,nextnode.y)) continue;vis[nextnode.x][nextnode.y] = 1;q.push(nextnode);}}return;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endif while (cin >> m >> n){if (m == 0) break;for (int i = 0;i < m;i++){cin >> s;for (int j = 0;j < n;j++)a[i][j] =( s[j] == '*') ? 0 : 1;}memset(vis, 0, sizeof(vis));ans = 0;for (int i = 0;i < m;i++)for (int j = 0;j < n;j++){if (a[i][j] && !vis[i][j])bfs(i, j);}cout << ans << endl;}return 0;
}DFS的写法：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <memory>using namespace std;const int maxn=110;
char pic[maxn][maxn];
int vis[maxn][maxn],ans,n,m;
int dir[8][2]={
{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};void dfs(int r,int c)
{for(int i=0;i<8;i++){int x=r+dir[i][0];int y=c+dir[i][1];if(x<1||x>n||y<1||y>m) continue;if(pic[x][y]=='@'&&!vis[x][y]){vis[x][y]=1;dfs(x,y);}}
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifwhile(cin>>n>>m){if(n==0) break;for(int i=1;i<=n;i++)scanf("%s",pic[i]+1);//注意dfs时行列下表都是从1开始的，所以要+1memset(vis,0,sizeof(vis));ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(pic[i][j]=='@'&&vis[i][j]==0){vis[i][j]=1;dfs(i,j);ans++;}}}cout<<ans<<endl;}return 0;
}