大家好,又见面了,我是你们的朋友全栈君。
八卦阵相传是由诸葛亮创设的一种战斗队形和兵力部署,由八种阵势组成。为了方便,采用矩阵来描述一个八卦阵,它由八个单阵组成,每个单阵由多个兵力区域组成形成一种阵势,如下图所示,其中数字为一个兵力区域的士兵个数。假设单阵与单阵之间兵力区域不会相邻,且单阵中每个兵力区域至少存在一个相邻兵力区域(注:相邻是指在其左上,正上,右上,右方,右下,正下,左下,左方与其相邻),请用最快的速度计算出八个单阵中的兵力(士兵个数)的最大值和最小值。
输入:
输入描述,例如:
第一行输入是八阵图的行数。
第二行输入是八阵图的列数。
后续行输入每个区域兵力。每一行的数据中间使用空格分开,当前一行输入完成后回车输入下一行数据。
输出:
输出描述,例如:
输出八个单阵中兵力最大值和最小值。
输入范例:
20
20
34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 30
0 23 10 5 5 0 0 0 5 5 5 5 5 0 0 0 30 0 40 0
0 9 0 0 5 0 0 0 4 4 4 4 4 0 0 0 0 30 0 0
0 8 7 7 0 5 0 0 3 3 3 3 0 0 0 0 7 0 9 0
0 9 0 0 5 0 5 0 0 12 12 0 0 0 0 10 0 0 0 9
0 0 0 0 5 0 0 5 0 12 12 0 0 5 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 12 12 0 0 5 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0
40 30 3 6 6 0 0 0 0 0 0 0 0 5 5 0 0 0 10 0
0 0 20 0 0 6 6 0 0 0 0 0 0 0 5 6 5 10 10 0
40 30 3 7 6 0 0 0 0 0 0 0 0 0 0 6 0 0 10 0
0 0 0 0 0 0 0 17 0 0 0 0 17 0 0 6 5 7 7 0
0 0 0 0 0 0 0 0 7 0 0 7 0 0 0 0 0 0 0 0
0 20 0 0 7 0 0 0 0 4 4 0 0 0 0 0 10 0 0 0
0 20 0 0 7 0 0 0 0 4 4 0 0 0 0 0 10 0 0 0
0 20 0 0 7 0 0 0 0 4 4 0 0 0 0 0 10 0 0 0
0 30 0 7 0 0 0 0 0 5 5 0 0 0 0 0 0 10 0 50
0 40 7 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 50 0
43 30 25 10 50 0 0 0 6 6 6 6 0 0 0 0 0 50 0 0
输出范例:
323
116
主要采用回溯算法,但是不知道为什么通过率只有20%,可能阿里的题确实太难了。不过这是第一次做出阿里的笔试题,例题跑通了感觉很开心。代码如下,Python写的:
n = int(raw_input()) m = int(raw_input()) a = [] bingli = [] zhuangtai = [[0 for x in range(m)] for y in range(n)] for i in range(n): a.append(list(map(int, raw_input().strip().split()))) def fangzhen(a, i, j): global count count += a[i][j] if i+1 <= 19 and j <= 19 and a[i+1][j] != 0 and zhuangtai[i+1][j] == 0: zhuangtai[i + 1][j] = 1 fangzhen(a, i+1, j) if i <= 19 and j+1 <= 19 and a[i][j+1] != 0 and zhuangtai[i][j+1] == 0: zhuangtai[i][j + 1] = 1 fangzhen(a, i, j+1) if i+1 <= 19 and j+1 <= 19 and a[i+1][j+1] != 0 and zhuangtai[i+1][j+1] == 0: zhuangtai[i + 1][j + 1] = 1 fangzhen(a, i+1, j+1) if i-1 >= 0 and j >= 0 and a[i-1][j] != 0 and zhuangtai[i-1][j] == 0: zhuangtai[i - 1][j] = 1 fangzhen(a, i-1, j) if i >= 0 and j-1 >= 0 and a[i][j-1] != 0 and zhuangtai[i][j-1] == 0: zhuangtai[i][j - 1] = 1 fangzhen(a, i, j-1) if i-1 >= 0 and j-1 >= 0 and a[i-1][j-1] != 0 and zhuangtai[i-1][j-1] == 0: zhuangtai[i - 1][j - 1] = 1 fangzhen(a, i-1, j-1) if i+1 <= 19 and j-1 >= 0 and a[i+1][j-1] != 0 and zhuangtai[i+1][j-1] == 0: zhuangtai[i + 1][j - 1] = 1 fangzhen(a, i+1, j-1) if i-1 >= 0 and j+1 <= 19 and a[i-1][j+1] != 0 and zhuangtai[i-1][j+1] == 0: zhuangtai[i - 1][j + 1] = 1 fangzhen(a, i-1, j+1) return count for i in range(n): for j in range(m): if a[i][j] != 0 and zhuangtai[i][j] == 0: zhuangtai[i][j] = 1 global count count = 0 fangzhen(a, i, j) bingli.append(count) bingli_max = max(bingli) bingli_min = min(bingli) print(bingli_max) print(bingli_min)
在下刚刚入门算法,萌新一枚,大家一起共勉。希望大佬不吝赐教。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/142413.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...