华为OD机试真题】68、矩阵扩散

1. package main
3. import (
4.         "errors"
5.         "fmt"
6.         "strconv"
7.         "strings"
8. )
10. type point struct {
11.         x     int
12.         y     int
13.         value int
14. }
16. type image struct {
17.         w        int
18.         h        int
19.         allPoint int
20.         points   [][]*point
21. }
23. func (i *image) newImage(m, n int) *image {
24.         img := make([][]*point, m)
25.         for i1 := 0; i1 < m; i1++ {
26.                 img[i1] = make([]*point, n)
27.                 for j := 0; j < n; j++ {
28.                         itemPoint := &point{
29.                                 x:     i1,
30.                                 y:     j,
31.                                 value: 0,
32.                         }
33.                         img[i1][j] = itemPoint
34.                 }
35.         }
37.         return &image{
38.                 w:        m,
39.                 h:        n,
40.                 allPoint: m * n,
41.                 points:   img,
42.         }
43. }
45. func (i *image) getPointValue(x, y int) (int, error) {
46.         for i1 := 0; i1 < i.w; i1++ {
47.                 for j := 0; j < i.h; j++ {
48.                         if i1 == x && j == y {
49.                                 return i.points[i1][j].value, nil
50.                         }
51.                 }
52.         }
54.         return 0, errors.New("not found")
55. }
57. func (i *image) setPointValue(p1 *point) (*image, error) {
58.         for i1 := 0; i1 < i.w; i1++ {
59.                 for j := 0; j < i.h; j++ {
60.                         if i1 == p1.x && j == p1.y {
61.                                 i.points[i1][j].value = p1.value
62.                                 return i, nil
63.                         }
64.                 }
65.         }
67.         return nil, errors.New("not found")
68. }
70. func (i *image) setPointsValue(list []*point, value int) {
71.         for _, p := range list {
72.                 p.value = value
73.                 i.setPointValue(p)
74.         }
75. }
77. func (i *image) countWaitePoints() (count int) {
78.         for i1 := 0; i1 < i.w; i1++ {
79.                 for j := 0; j < i.h; j++ {
80.                         if i.points[i1][j].value == 1 {
81.                                 count++
82.                         }
83.                 }
84.         }
85.         return
86. }
88. func (i *image) isAllWaite() bool {
89.         if i.countWaitePoints() == i.allPoint {
90.                 return true
91.         }
92.         return false
93. }
95. // 获取一个点周围的非白色像素点
96. func (i *image) listAroundNotWaitePoints(p1 *point) []*point {
97.         list := make([]*point, 0)
98.         centerX, centreY := p1.x, p1.y
99.         for x := -1; x <= 1; x++ {
100.                 for y := -1; y <= 1; y++ {
101.                         if x != 0 && y != 0 {
102.                                 continue
103.                         }
105.                         itemX := centerX + x
106.                         itemY := centreY + y
107.                         //溢出
108.                         if itemX*itemY < 0 {
109.                                 continue
110.                         }
111.                         if value, err := i.getPointValue(itemX, itemY); err == nil {
112.                                 if value != 1 {
113.                                         list = append(list, &point{
114.                                                 x:     itemX,
115.                                                 y:     itemY,
116.                                                 value: i.points[itemX][itemY].value,
117.                                         })
118.                                 }
119.                         }
121.                 }
122.         }
124.         return list
125. }
127. func (i *image) listWaitePoints() []*point {
128.         list := make([]*point, 0)
130.         for i1 := 0; i1 < i.w; i1++ {
131.                 for j := 0; j < i.h; j++ {
132.                         if i.points[i1][j].value == 1 {
133.                                 list = append(list, &point{
134.                                         x:     i1,
135.                                         y:     j,
136.                                         value: i.points[i1][j].value,
137.                                 })
138.                         }
139.                 }
140.         }
142.         return list
143. }
145. func (i *image) timer(count int) int {
146.         if i.isAllWaite() {
147.                 return count
148.         } else {
149.                 count++
151.                 waitePoints := i.listWaitePoints()
152.                 for _, waitePoint := range waitePoints {
153.                         //开始膨胀
154.                         if notWaitePoints := i.listAroundNotWaitePoints(waitePoint); len(notWaitePoints) > 0 {
155.                                 i.setPointsValue(notWaitePoints, 1)
156.                         }
157.                 }
158.                 return i.timer(count)
159.         }
161. }
163. func main() {
164.         var inputStr string
165.         fmt.Scan(&inputStr)
166.         inputStrList := strings.Split(inputStr, ",")
167.         inputIntList := make([]int, len(inputStrList))
168.         for i, s2 := range inputStrList {
169.                 inputIntList[i], _ = strconv.Atoi(s2)
170.         }
172.         var m, n int
173.         m = inputIntList[0]
174.         n = inputIntList[1]
176.         myImage := new(image)
177.         img := myImage.newImage(m, n)
178.         img.setPointValue(&point{
179.                 x:     inputIntList[2],
180.                 y:     inputIntList[3],
181.                 value: 1,
182.         })
183.         img.setPointValue(&point{
184.                 x:     inputIntList[4],
185.                 y:     inputIntList[5],
186.                 value: 1,
187.         })
189.         count := img.timer(0)
190.         fmt.Println(count)
192. }

复制代码

总结：矩阵扩散在图形图像中被称为膨胀，结合openCV中对图片和像素点的界说，在程序中我界说了两种struct: image 和point，并实现了膨胀系数为1的膨胀算法。在通过递归的方式不断执行膨胀操纵，知道全部点都变白，则停止递归，每次膨胀时计数器timer加一，递归竣过后返回timer.

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。