求联通个数

给定一个数组,数组元素=w表示是水,=.表示没有水
如果w的周围8个位置有w,那么他们属于一个水洼
问有几个水洼

下面是一个输入,输出应该是3

解法1

就是当碰到某个水点的时候,深度优先地将所有与之联通的水点都变成陆点
这样就相当于是消除了一个水洼

1#include<iostream>
2using namespace std;
3 
4const int MAX_N = 100;
5const int MAX_M = 100;
6 
7char map[MAX_N][MAX_M];
8int n, m;
9 
10void input_data() {
11    int i, j;
12  for(i=0; i<MAX_N; i++) {
13    for(j=0; j<MAX_M; j++) {
14      map[i][j] = '.';
15    }
16  }
17  
18  n = 10;
19  m = 12;
20  
21  map[0][0] = map[0][9] = map[0][10] = 'w';
22  map[1][1] = map[1][2] = map[1][3] 
23              = map[1][9] = map[1][10] 
24              = map[1][11] = 'w';
25  map[2][4] = map[2][5] = map[2][9] = map[2][10] = 'w';
26  map[3][9] = map[3][10] = 'w';
27  map[4][9] = 'w';
28  map[5][2] = map[5][9] = 'w';
29  map[6][1] = map[6][3] = map[6][9] = map[6][10] = 'w';
30  map[7][0] = map[7][2] = map[7][4] = map[7][10] = 'w';
31  map[8][1] = map[8][3] = map[8][9] = map[8][10] = 'w';
32  map[9][2] = map[9][10] = 'w';
33}
34 
35void output_data() {
36    cout << "n = " << n << ", m = " << m << endl;
37    for (int i = 0; i < n; ++i){
38        for (int j = 0; j < m; ++j){
39            cout << map[i][j];
40        }
41        cout << endl;
42    }
43    cout << endl;
44}
45
46// 将所有与(x, y)联通的点都变成陆地
47void dfs(int x, int y) {
48    map[x][y] = '.';
49 
50    int tx, ty;
51 
52    for (int i = -1; i <= 1; ++i){
53        for (int j = -1; j <= 1; ++j){
54            tx = x + i;
55            ty = y + j;
56            if (tx >= 0 && tx < n && ty >= 0 && ty < m && map[tx][ty] == 'w'){
57                dfs(tx, ty);
58            }
59        }
60    }
61 
62    return;
63}
64 
65void solve() {
66    int num = 0;
67 
68    for (int i = 0; i < n; ++i){
69        for (int j = 0; j < m; ++j){
70            if (map[i][j] == 'w'){
71                dfs(i, j);
72                num++;
73            }
74        }
75    }
76 
77    cout << "the num is " << num << endl;
78}
79 
80int main() {
81    input_data();
82    solve();
83 
84    return 0;
85}
#include<iostream>

using namespace std;

 

const int MAX_N = 100;

const int MAX_M = 100;

 

char map[MAX_N][MAX_M];

int n, m;

 

void input_data() {

    int i, j;

	for(i=0; i<MAX_N; i++) {

		for(j=0; j<MAX_M; j++) {

			map[i][j] = '.';

		}

	}

	

	n = 10;

	m = 12;

	

	map[0][0] = map[0][9] = map[0][10] = 'w';

	map[1][1] = map[1][2] = map[1][3] 

              = map[1][9] = map[1][10] 

              = map[1][11] = 'w';

	map[2][4] = map[2][5] = map[2][9] = map[2][10] = 'w';

	map[3][9] = map[3][10] = 'w';

	map[4][9] = 'w';

	map[5][2] = map[5][9] = 'w';

	map[6][1] = map[6][3] = map[6][9] = map[6][10] = 'w';

	map[7][0] = map[7][2] = map[7][4] = map[7][10] = 'w';

	map[8][1] = map[8][3] = map[8][9] = map[8][10] = 'w';

	map[9][2] = map[9][10] = 'w';

}

 

void output_data() {

    cout << "n = " << n << ", m = " << m << endl;

    for (int i = 0; i < n; ++i){

        for (int j = 0; j < m; ++j){

            cout << map[i][j];

        }

        cout << endl;

    }

    cout << endl;

}



// 将所有与(x, y)联通的点都变成陆地

void dfs(int x, int y) {

    map[x][y] = '.';

 

    int tx, ty;

 

    for (int i = -1; i <= 1; ++i){

        for (int j = -1; j <= 1; ++j){

            tx = x + i;

            ty = y + j;

            if (tx >= 0 && tx < n && ty >= 0 && ty < m && map[tx][ty] == 'w'){

                dfs(tx, ty);

            }

        }

    }

 

    return;

}

 

void solve() {

    int num = 0;

 

    for (int i = 0; i < n; ++i){

        for (int j = 0; j < m; ++j){

            if (map[i][j] == 'w'){

                dfs(i, j);

                num++;

            }

        }

    }

 

    cout << "the num is " << num << endl;

}

 

int main() {

    input_data();

    solve();

 

    return 0;

}


如果有任何问题请发邮件到 isteps@126.com


广告内容, 如果不忙, 跪求点击