2018阿里笔试题一道

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)

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/142413.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 动态因果图模型_因果图是谁提出来的

    动态因果图模型_因果图是谁提出来的文章目录1.动态因果图模型1.1引言1.1.1信度网的应用与不足1.1.2因果图的优势1.2模型主要思想1.3模型的表达方式1.3.1因果图与故障诊断1.3.2因果图分类1.3.3因果图形式化表示1.3.4因果图的正规化1.4因果树1.4.1微因果树1.4.2因果树与因果图对比2.动态因果图推理2.1待求解问题的数学形式2.2割集2.2.1一阶割集2.2.2最终割集2.3因果图编译2.3.1逻辑解环2.3.2求最终割集式2.3.3求不交化割集2.4因果图计算简化2

  • G1收集器详解「建议收藏」

    G1收集器详解「建议收藏」CMS垃圾收集器的弊端:会产生内存碎片&&需要预留空间。这两个问题在处理时,很有可能会导致停顿时间过长,即CMS的停顿时间不可预知。所以G1又可以理解为在CMS垃圾收集器上进行了”升级”。G1垃圾收集器可以给你设定一个你希望Stoptheworld停顿时间,G1会根据这个时间尽量满足你。在JVM堆中,堆的内存分布是以物理空间进行隔离——但是在G1垃圾收集器中,堆的划分不再是物理形式,而是以逻辑的形式进行划分。但是,分代的概念在G1中依旧奏效,比如,新对象一般会被分配.

  • windows下怎么安装laravel框架

    windows下怎么安装laravel框架windows下怎么安装laravel框架

  • 企业微信api接口,企业微信sdk

    企业微信api接口,企业微信sdk企业微信api接口,企业微信sdk1、企业微信SDK接口API调用-企业微信好友收发消息/***给企业微信好友发消息*@authorwechat:happybabby110*@bloghttp://www.wlkankan.cn*/@AsyncpublicvoidhandleMsg(ChannelHandlerContextctx,TransportMessagevo,StringcontentJ…

  • RSA算法详解_warshall算法

    RSA算法详解_warshall算法一、概述RSA算法是1977年由RonRivest、AdiShamir和LeonardAdleman三人组在论文AMethodforObtainingDigitalSignatu

  • win10下pycharm+Qtdesigner+Pyqt 成功配置

    win10下pycharm+Qtdesigner+Pyqt 成功配置请在安装之前,将整个博客看完之后再进行操作!我的安装过程有点曲折//使用Qtdesigner做可视化的界面设计,是一项很强大的工具。今天用到了,就在pycharm下配置一下,随手做点记录Qtdesigner可以可视化拖动生成界面。我的环境:win10pycharm+anaconda(python3.6.4)配置过程:1.在安装pyqt5的时候需要有sip的支持,sip…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号