2018阿里笔试题一道

大家好，又见面了，我是你们的朋友全栈君。

八卦阵相传是由诸葛亮创设的一种战斗队形和兵力部署，由八种阵势组成。为了方便，采用矩阵来描述一个八卦阵，它由八个单阵组成，每个单阵由多个兵力区域组成形成一种阵势，如下图所示，其中数字为一个兵力区域的士兵个数。假设单阵与单阵之间兵力区域不会相邻，且单阵中每个兵力区域至少存在一个相邻兵力区域（注：相邻是指在其左上，正上，右上，右方，右下，正下，左下，左方与其相邻），请用最快的速度计算出八个单阵中的兵力（士兵个数）的最大值和最小值。

输入: 输入描述，例如： 第一行输入是八阵图的行数。 第二行输入是八阵图的列数。 后续行输入每个区域兵力。每一行的数据中间使用空格分开，当前一行输入完成后回车输入下一行数据。 输出: 输出描述，例如： 输出八个单阵中兵力最大值和最小值。 输入范例: 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)

在下刚刚入门算法，萌新一枚，大家一起共勉。希望大佬不吝赐教。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/142413.html原文链接：https://javaforall.cn