HDU1241——Oil Deposits

http://acm.hdu.edu.cn/showproblem.php?pid=1241

这道题类似HDU2952,只是增加对角线的点可以被访问就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
//泼水原理
/*
要注意的:
1.用vis数组记录访问过的位置，其目的是减少访问量，
一般bfs会出现Memory limit exceed，加到队列里面的节点都要占空间，扩展的节点太多就爆内存
2.一定要在访问过后就立刻标记，而不是在第二次查找下边的点的时候才把当前点标记访问过。
3.用vis数组标记和将图中标记为不可访问的效果是一样的。 
*/ 
//请审题！！！ 
using namespace std;
void bfs(int s,int t);
struct point{
    int x,y;
};
    queue<point> que;
int dx[] = {1, -1, 0, 0,1,-1,1,-1};
int dy[] = {0, 0, 1, -1,1,1,-1,-1};
int a,b;
char G[101][101];
int main(){
    int n,ans;
     while(~scanf("%d%d",&a,&b)&&a!=0&&b!=0){
         for(int x=0;x<a;x++){
             scanf("%s",G[x]); 
         }
         ans=0;
         for(int i=0;i<a;i++){
             for(int j=0;j<b;j++){
                 if(G[i][j]=='@'){
                     bfs(i,j);
                     ans++;
                 }
             }
         }
         printf("%d
",ans);
     }
    return 0;
}
void bfs(int s,int t){
    point start;
    start.x=s;
    start.y=t;
    que.push(start);
    G[s][t]='.';
    while(!que.empty()){
        point p=que.front();
        que.pop();
        for(int i=0;i<8;i++){
            int xx=p.x+dx[i];
            int yy=p.y+dy[i];
            if(xx<0||xx>=a)continue;
            if(yy<0||yy>=b)continue;
            if(G[xx][yy]=='*')continue;
            point r;
            r.x=xx;
            r.y=yy;
            que.push(r);
            G[xx][yy]='*'; 
        }
    }    
}