首页 > 代码库 > poj-1562
poj-1562
题意:
求途中的连通分量,一个点的八个方向相连都算一个连通分量。
Sample Input
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0
Sample Output
0 1 2 2
Sample Input
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0
Sample Output
0 1 2 2
解题思路:
bfs
具体代码:
#include<iostream> #include<cstring> #include<queue> using namespace std; char map[105][105]; int m,n; int fangxiang[8][2]={{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}}; struct Node { int x; int y; Node(int x1,int y1):x(x1),y(y1){} }; void bfs(int i,int j) { Node node(i,j); queue<Node> q; while(!q.empty()) q.pop(); q.push(node); while(!q.empty()) { node=q.front(); q.pop(); for(int k=0;k<8;k++) { int xx=node.x+fangxiang[k][0]; int yy=node.y+fangxiang[k][1]; if(xx>=0&&xx<m&&yy>=0&&yy<n&&map[xx][yy]==‘@‘) { map[xx][yy]=‘*‘; Node temp(xx,yy); q.push(temp); } } } } int main() { while(1) { cin>>m>>n; int sum=0; if(m==0&&n==0) break; for(int i=0;i<m;i++) for(int j=0;j<n;j++) cin>>map[i][j]; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(map[i][j]==‘@‘) { sum++; bfs(i,j); } } } cout<<sum<<endl; } system("pause"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。