题目的来源是给定一张图片，查找所有临近的像素点，并求出最大像素值。经过抽象后是：两个矩阵，一个只是包含0 1,另一个是每个位置具体的像素值，可以通过查找第一个矩阵来确定连通域的点，根据第二个矩阵得出最大的值。

矩阵1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# data
1 0 0 0 1 0 0 0 0 1
0 1 0 0 1 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 1 0 0 1 0 0 0 0 0

矩阵2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# data2
1 0 0 0 1 0 0 0 0 1
0 2 0 0 3 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 4 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 5 1 1 0
0 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
0 6 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 7 0 0 8 0 0 0 0 0

C++代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
// recursionFindPoints.cpp

#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef double    db;

long flag = 2;
long START = flag;

int recursion(ll i, ll j, vector<vector<ll> > &data, vector<pair<ll,ll> > &position);
int launch( vector<vector<ll> > &data, vector<vector<db> > &data2);

int main(int argc, char * argv[])
{
    if (argc != 3)
    {
        cout<<"Enter two file"<<endl;
        return -1;
    }
    // 1 read map and intensity
    ifstream fin(argv[1]);
    ifstream fin2(argv[2]);

    vector<vector<ll> > data;
    vector<vector<db> > data2;
    vector<ll> temp;
    ll v;
    vector<db> temp2;
    db d;

    string line;
    string value;
    while (getline(fin,line))
    {
        stringstream ss(line);
        while (getline(ss,value,' '))
        {
           v = atoi(value.c_str());  
           temp.push_back(v);
        }
        data.push_back(temp);
        temp.clear();
    }	

    while (getline(fin2,line))
    {
        stringstream ss(line);
        while (getline(ss,value,' '))
        {
           d = atoi(value.c_str());  
           temp2.push_back(d);
        }
        data2.push_back(temp2);
        temp2.clear();
    }	

    // 2 entrance
    launch(data,data2);

    // 3 output result
    for (vector<vector<ll> >::iterator it = data.begin(); it != data.end(); ++it)
    {
        for (vector<ll>::iterator i = (*it).begin(); i != (*it).end(); ++i)
            cout<<*i<<" ";
        cout<<endl;
    }

}

int launch(vector<vector<ll> > &data, vector<vector<db> > &data2)
{
    // 1. Find all points in connected domain and store these coordinate
    vector<vector<pair<ll,ll> > > result;
    vector<pair<ll,ll> >  temp;
    for (int i = 0; i < data.size(); ++i)
    {
        for (int j = 0; j < data[0].size(); ++j)
        {
            if (data[i][j] == 1)
            {
               temp.push_back(make_pair(i,j)); 
               data[i][j] = flag;
               recursion(i,j,data,temp);
               flag++;
               result.push_back(temp);
               temp.clear();
            }
        }
    }

    // 2. Filter
    pair<ll,ll> pos;
    db inten = 0;
    for (vector<vector<pair<ll,ll> > >::iterator it = result.begin(); it != result.end(); ++it)
    {
        for (vector<pair<ll, ll> >::iterator jt = (*it).begin(); jt != (*it).end(); ++jt)
        {
            // cout<<(*jt).first<<" "<<(*jt).second<<"    ";
            if (inten <= data2[(*jt).first][(*jt).second])
            {
                inten = data2[(*jt).first][(*jt).second];
                pos.first = (*jt).first;
                pos.second = (*jt).second;
            }
        }
        // cout<<endl;
        printf("The %d points's max intensity is: %d\n", int(START), int(inten));
        START ++;
        inten = 0;
    }

    return 0;
}

int recursion(ll i, ll j, vector<vector<ll> > &data, vector<pair<ll,ll> > &position)
{
    for (int x = i - 1; x <= i + 1; x++)
    {
        for (int y = j - 1; y <= j + 1; y++)
        {
            if (x == i && y == j)
                continue;
            if (x >= 0 && x < data.size() && y >= 0 && y < data[0].size() && data[x][y] == 1)
            {
                position.push_back(make_pair(x, y));
                data[x][y] = flag;
                recursion(x,y,data,position);
            }
        }
    }
    return 0;
}

运行程序及结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$ g++ recursionFindPoints.cpp -o rfp
$ ./rfp data data2
The 2 points's max intensity is: 2
The 3 points's max intensity is: 3
The 4 points's max intensity is: 1
The 5 points's max intensity is: 1
The 6 points's max intensity is: 4
The 7 points's max intensity is: 1
The 8 points's max intensity is: 5
The 9 points's max intensity is: 6
The 10 points's max intensity is: 1
The 11 points's max intensity is: 1
The 12 points's max intensity is: 7
The 13 points's max intensity is: 8
2 0 0 0 3 0 0 0 0 4 
0 2 0 0 3 0 0 0 0 0 
0 2 2 0 3 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 5 
0 0 0 0 6 0 0 0 0 0 
0 0 0 6 0 0 0 0 0 0 
7 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 8 8 0 0 0 
0 0 0 0 0 0 8 8 8 0 
0 0 0 0 0 0 0 0 0 8 
9 0 0 0 10 0 0 0 0 8 
0 9 0 0 10 0 0 0 0 0 
0 0 0 0 0 0 0 11 0 0 
0 12 0 0 13 0 0 0 0 0

运行结果分两部分，第一部分是找到的每个连通域中点的最大值，第二部分是在第一个矩阵的基础上对连通域进行标号区分之后的矩阵

程序使用递归来查找一个九宫格的中心对周围八个点的关系，几行代码即可实现，可见递归的精妙，缺点是递归有最大层数，如果超过了会导致堆栈溢出，所以不能应用于太大的矩阵