poj 2386 Lake Counting——BFS（队列）

蔚落 2023-01-16 09:42 96阅读 0赞

题意：要数出池塘的数量，‘W’表示水，‘.’表示陆地。

思路：2个for循环遍历一遍，每一次选择是  ‘W’  且没被访问过的进行BFS搜索，搜索时可以走8个方向。

int dir[8][2]={
       {1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

源代码：

#include<stdio.h>
    #include<string.h>
    int n,m,i,j,k,num,front,rear;
    char data[205][205];
    int vis[205][205]; 
    int dir[8][2]={ { 1,0},{ 1,1},{ 0,1},{ -1,1},{ -1,0},{ -1,-1},{ 0,-1},{ 1,-1}};
    struct ED
    { 
    	int x,y;
    }queue[10005],e;
    void bfs()
    { 
    	int i,j,xx,yy;
    	num=0;
    	for(i=0;i<n;i++)
    	 for(j=0;j<m;j++)
    	 if(vis[i][j]==0&&data[i][j]=='W')
    	 { 
    		 front=rear=0;
    		 queue[front].x=i;
    	     queue[front].y=j;
    	   while(front<=rear)
    	   { 
    		xx=queue[front].x;
    		yy=queue[front].y;
    		front++;
    		for(int l=0;l<8;l++)
    		{ 
    			e.x=xx+dir[l][0];
    			e.y=yy+dir[l][1];;
    			if(vis[e.x][e.y]==0 && data[e.x][e.y]=='W' &&

e.x>=0 && e.x<n && e.y>=0 && e.y<m)
    			{ 
    				++rear;
    				queue[rear]=e;
    				vis[e.x][e.y]=1; 
    			}
    		}
    	   }
    	   num++;
    	 }
    	printf("%d\n",num);
    }
    int main()  // Lake Counting
    { 
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{ 
    		memset(vis,0,sizeof(vis));
    		memset(data,-1,sizeof(data));
    		memset(queue,-1,sizeof(queue));
    		getchar();
    		for(i=0;i<n;i++)
    		  scanf("%s",data[i]);	
    	        bfs();
    	}
      return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj 2386 Lake Counting——BFS（队列）

题意：要数出池塘的数量，‘W’表示水，‘.’表示陆地。思路：2个for循环遍历一遍，每一次选择是 ‘W’ 且没被访问过的进行BFS搜索，搜索时可以走8个方向。

蔚落/ 2023年01月16日 09:42/ 0 赞/ 97 阅读

相关【队列栈】 POJ1363 Rails

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

分手后的思念是犯贱/ 2022年12月02日 15:25/ 0 赞/ 78 阅读

相关 POJ 2386 Lake Counting（经典dfs）

Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 33538 Accep

系统管理员/ 2022年09月30日 13:53/ 0 赞/ 13 阅读

相关 Data Lake

Data Lake Data Lake is a term that’s appeared in this decade to describe an important

你的名字/ 2022年09月11日 07:17/ 0 赞/ 9 阅读

相关 poj 2386（深搜或广搜）

Lake Counting <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000M

偏执的太偏执、/ 2022年08月25日 13:46/ 0 赞/ 217 阅读

相关 Avoid The Lakes--poj3620

Avoid The Lakes <table style="margin-left: auto; margin-right: auto;"> <tbody> <tr

ゝ一世哀愁。/ 2022年08月04日 08:57/ 0 赞/ 2 阅读

相关 POJ 2386 Lake Counting【DFS】

Lake Counting Description Due to recent rains, water has pooled in various places i

野性酷女/ 2022年06月17日 00:37/ 0 赞/ 124 阅读

相关 POJ 2386 Lake Counting

Due to recent rains, water has pooled in various places in Farmer John's field, which is

╰+攻爆jí腚メ/ 2022年03月12日 02:28/ 0 赞/ 108 阅读

相关 POJ 3629 队列模拟

听说STL会卡T 然后我就试了一发哈哈哈哈哈哈哈哈哈哈 1000ms卡时过的这很值得我写一发题解了哈哈哈哈哈哈哈哈哈哈哈哈 //By SiriusRen

Myth丶恋晨/ 2021年12月22日 14:17/ 0 赞/ 228 阅读

相关 Lake Counting

Description Due to recent rains, water has pooled in various places in Farmer John's fi

谁践踏了优雅/ 2021年06月24日 13:58/ 0 赞/ 266 阅读