首页 > 代码库 > nyoj-27-水池数目
nyoj-27-水池数目
1 //题目地址:http://acm.nyist.net/JudgeOnline/status.php?pid=27
2 //解题思路:裸的dfs, 遍历每个格子dfs访问当前格子的相领格子
3 #include <stdio.h>
4 #include <string.h>
5
6 int map[110][110], vis[110][110];
7 int dx[4] = {0, 0, -1, 1};
8 int dy[4] = {-1, 1, 0, 0};
9
10 void dfs(int x, int y){
11 int i;
12 if(map[x][y] == 0 || vis[x][y] == 1) return ; //访问过,或者不存在水池则返回
13 vis[x][y] = 1;
14 for(i = 0; i <4; i++){
15 dfs(x + dx[i], y + dy[i]);
16 }
17 // dfs(x - 1, y);
18 // dfs(x +1, y);
19 // dfs(x, y - 1);
20 // dfs(x, y + 1);
21 }
22
23 int main(){
24 int t, n, m, i, j;
25 int ans;
26 scanf("%d", &t);
27 while(t--){
28 scanf("%d %d", &n, &m);
29 memset(map, 0, sizeof(map));
30 memset(vis, 0, sizeof(vis));
31 for(i = 1; i <= n; i++){
32 for(j = 1; j <= m; j++){
33 scanf("%d", &map[i][j]);
34 }
35 }
36 ans = 0;
37 for(i = 1; i <= n; i++){
38 for(j = 1; j <= m; j++){
39 if(map[i][j] == 1 && vis[i][j] == 0){
40 ans++;
41 dfs(i, j);
42 }
43 }
44 }
45 printf("%d\n", ans);
46 }
47 return 0;
48 }
2 //解题思路:裸的dfs, 遍历每个格子dfs访问当前格子的相领格子
3 #include <stdio.h>
4 #include <string.h>
5
6 int map[110][110], vis[110][110];
7 int dx[4] = {0, 0, -1, 1};
8 int dy[4] = {-1, 1, 0, 0};
9
10 void dfs(int x, int y){
11 int i;
12 if(map[x][y] == 0 || vis[x][y] == 1) return ; //访问过,或者不存在水池则返回
13 vis[x][y] = 1;
14 for(i = 0; i <4; i++){
15 dfs(x + dx[i], y + dy[i]);
16 }
17 // dfs(x - 1, y);
18 // dfs(x +1, y);
19 // dfs(x, y - 1);
20 // dfs(x, y + 1);
21 }
22
23 int main(){
24 int t, n, m, i, j;
25 int ans;
26 scanf("%d", &t);
27 while(t--){
28 scanf("%d %d", &n, &m);
29 memset(map, 0, sizeof(map));
30 memset(vis, 0, sizeof(vis));
31 for(i = 1; i <= n; i++){
32 for(j = 1; j <= m; j++){
33 scanf("%d", &map[i][j]);
34 }
35 }
36 ans = 0;
37 for(i = 1; i <= n; i++){
38 for(j = 1; j <= m; j++){
39 if(map[i][j] == 1 && vis[i][j] == 0){
40 ans++;
41 dfs(i, j);
42 }
43 }
44 }
45 printf("%d\n", ans);
46 }
47 return 0;
48 }
nyoj-27-水池数目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。