要求：
1. 有N 行，M列整数数字存储在一个txt文件中（如下），每个数字都不重复，同行数字用空格分开（可能为N个空格），将其从文件中读取出来。
2. 以最大的数值作为起点，开始连线，每个数字只能连接其上下左右4个点中的一个，且所连数字必须比当前数字小，求用一条线所能连接的数字的最大个数（注意：不是最大和），输出个数及所连接的数字。
3. 考虑执行效率。
示例： 如文件中存储为如下格式，则25作为起点，可以做25-18-3或25-20-19-4连线
，而所求的最长连线应为: 25-24-23-22….3-2-1， 共25个。
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
代码：
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func check(x, y, m, n int) bool {
if x < 0 || x >= n || y < 0 || y >= m {
// fmt.Print("true", "\n")
return true
}
// fmt.Print("false", "\n")
return false
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func dp(r, c, a, b, maxx int, ma [100][]int, le [100][]int) int {
dir := [4][2]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
// var s = [4][]int{{ma[r][c]}, {ma[r][c]}, {ma[r][c]}, {ma[r][c]}}
maxx = 0
temx, temy, t := 0, 0, 0
for t = 0; t < 4; t++ {
temx = r + dir[t][0]
temy = c + dir[t][1]
// fmt.Print(temx, temy)
// fmt.Print(ma[temx][temy])
if check(temx, temy, a, b) || (ma[temx][temy] > ma[r][c]) {
// fmt.Print(ma[r][c])
// fmt.Print("continue")
continue
}
// fmt.Print(ma[temx][temy], "\n")
// s[i] = append(s[i], ma[temx][temy])
maxx = max(maxx, dp(temx, temy, a, b, maxx, ma, le))
// fmt.Print(maxx, "\n")
}
le[r][c] = maxx + 1
// fmt.Print("***", le[r][c], "***")
return le[r][c]
}
func main() {
inputFile, err := os.Open("test1.txt")
if err != nil {
panic(err)
}
defer inputFile.Close()
buf := bufio.NewReader(inputFile)
i, j := 0, 0
// c, r := 0, 0
var ma, le [100][]int
for {
line, err := buf.ReadString('\n')
line = strings.TrimSpace(line)
a := strings.Fields(line)
// print(line, "\n")
for j = 0; j < len(a); j++ {
v, err := strconv.Atoi(a[j])
if err != nil {
panic(err)
}
ma[i] = append(ma[i], v)
le[i] = append(le[i], 0)
// print(ma[i][j], "\n")
// print(le[i][j], "\n")
}
i = i + 1
if err != nil {
if err != nil {
break
}
}
}
// print("****", i, j, "\n")
s1, s2 := getMaxnum(i, j, ma)
maxx := -1
maxx = max(maxx, dp(s1, s2, j, i, maxx, ma, le))
fmt.Print("###", maxx, "###")
}
func getMaxnum(a, b int, s [100][]int) (a1, b1 int) {
max := 0
var q1, q2 int
for i1 := 0; i1 < a; i1++ {
for j1 := 0; j1 < b; j1++ {
if s[i1][j1] > max {
max = s[i1][j1]
q1 = i1
q2 = j1
}
}
}
return q1, q2
}
只能得到最长路径的值，无法获得最长路径
更多评论
今日阅读排行
一周阅读排行