首页 > 代码库 > UVa 572 油田(DFS求连通块)
UVa 572 油田(DFS求连通块)
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=513
终于开始接触图了,恩,开始接触DFS了,这道题就是求连通分量,比较简单。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 int m, n; //记录连通块的数量 6 char a[10000][10000]; 7 int b[10000][10000]; 8 9 void DFS(int i, int j, int count) 10 { 11 if (i < 0 || i >= m || j < 0 || j >= n) return; //在递归时出界的情况 12 if(b[i][j]>0 || a[i][j]!=‘@‘) return; 13 b[i][j] = count; 14 for (int p = -1; p <= 1; p++) 15 { 16 for (int q = -1; q <= 1; q++) 17 { 18 if (p != 0||q != 0) DFS(i + p, j + q, count); 19 } 20 } 21 } 22 23 int main() 24 { 25 while (cin >> m >> n && m && n) 26 { 27 for (int i = 0; i < m; i++) 28 scanf("%s", &a[i]); 29 int count = 0; 30 memset(b, 0, sizeof(b)); 31 for (int i = 0; i < m; i++) 32 { 33 for (int j = 0; j < n; j++) 34 { 35 if (b[i][j] == 0 && a[i][j]==‘@‘) DFS(i, j, ++count); 36 } 37 } 38 cout << count << endl; 39 } 40 return 0; 41 }
2016-12-03 07:49:56
UVa 572 油田(DFS求连通块)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。