首页 > 其他 > 详细

poj2386---Lake Counting

时间:2018-08-17 22:03:09      阅读:139      评论:0      收藏:0      [点我收藏+]

tips:

  1.统计进行了几次bfs,判断队首结点的相邻结点是否符合入队条件单独写成一个judge函数

  2.使用memset函数要包含<cstring>

技术分享图片
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=105;
struct node{
    int x;int y;
}Node;
int matrix[M][M];
bool inq[M][M];
int n,m;
int x[8]={-1,-1,-1,0,0,1,1,1};
int y[8]={1,0,-1,1,-1,1,0,-1};
bool judge(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m ) return false;
    if(matrix[x][y] == . || inq[x][y]== 1) return false;
    return true;
}
void BFS(int a,int b){
  queue<node> Q;
  Node.x=a,Node.y=b;
  Q.push(Node);
  inq[a][b]=1;
  while(!Q.empty()){
    node top=Q.front();
    Q.pop();
    for(int i=0;i<8;i++){
        int dx=top.x+x[i];
        int dy=top.y+y[i];
        if(judge(dx,dy)){
            Node.x=dx,Node.y=dy;
            Q.push(Node);
            inq[dx][dy]=1;
        }
    }


   }
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
            getchar();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%c",&matrix[i][j]);
            }
            getchar();
        }
        memset(inq,0,sizeof(inq));
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0; j<m;j++){
                if(matrix[i][j]== W && inq[i][j]==0){
                    ans++;
                    BFS(i,j);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

 

poj2386---Lake Counting

原文:https://www.cnblogs.com/SUMaywlx/p/9495321.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!