【算法题】螺旋矩阵III (求解n阶蛇形矩阵)

2023-11-09

一、问题的提出

n阶蛇形矩阵的特点是按照图1所示的方式排列元素。n阶蛇形矩阵是指矩阵的大小为n×n,其中n为正整数。

题目背景

一个 n  n 列的螺旋矩阵可由如图1所示的方法生成,观察图片,找出填数规律。填数规则为从 1 开始填到 n×n

图1  n  n 列的螺旋矩阵(蛇形矩阵)

 现在给出矩阵大小 n 以及 i  j,请你求出该矩阵中第 i 行第 j 列的数是多少。

题目描述

输入格式

从标准输入读入数据。 共一行,包含三个整数 n1n1,000)、i1in)、j1jn),每两个整数之间用一个空格隔开,分别表示矩阵大小、待求的数所在的行号和列号。

输出格式

输出到标准输出。 一个整数,表示相应矩阵中第 i 行第 j 列的数。

输入输出样例

输入 #1复制

8 2 8

输出 #1复制

43

说明/提示

子任务

  • 对于 30% 的测试数据,n10
  • 对于 60% 的测试数据,n100
  • 对于 100% 的测试数据,n1,000
  • 特别地,对于 20% 的测试数据,i=j=1

提示

根据本题的填数规则,一个 8×8 的螺旋矩阵应该长这样(如图2所示):

图2 88列的螺旋矩阵(蛇形矩阵)

 二、解题的思路

由图3可知,这是个旋转45º的Z形矩阵,当然折返长度是不相等的。仔细看图1发现:当向右上方填数时,如行号为0则向右(行号不变,列号加1),如是列号到n时则向下(列号减1,行号加1),然后向左下方填数,此时,如列号为0则向下,如是行号到n时则向右(行号减1,列号加1),然后向右一方填数,如此重复直到最后行、最后列填完为止。

图3 蛇形矩阵分析图

三、矩阵生成算法

nn列,第一行为0行,第一列为0列。从(0,0)1开始,方向设为从左下往右上。

当从左下往右上时,如行号已为0则列号加1方向向反(从右上往左下),否则行号减1,列号加1,如列号达n则列号为n-1,行号加1方向向反(从右上往左下)

当从右上往左下时,如列号已为0则行号加1方向向反(从左下往右上),否则行号加1,列号减1,如行号达n则列号加1,行号为n-1方向向反(从左下往右上)

当行号和列号都为n-1时结束。

程序代码如下:

def prt(hm):                 # 打印二维列表
    for i in range(N):
        for j in range(N):
            print("%3d" % hm[i][j], end='')
        print()
 
def Helix_MatrixII(n):
    cnt = 1
    i = j = 0
    k = 1
    while True:
        matrix[i][j] = cnt
        if i == n-1 and j == n-1:
            break
        if k == 1:           # 从左下往右上 
            if i == 0 :
                j += 1
                if j >= n:
                    j = n-1
                    i = i+1 if i < n -1 else n-1
                k = -1
            elif j == n-1:
                i += 1
                k = -1
            else:
                i -= 1
                j += 1
        else:                # 从右上往左下
            if j == 0 :
                i += 1
                if i >= n:
                    i = n-1
                    j = j+1 if j < n -1 else n-1
                k = 1
            elif i == n-1:
                j += 1
                k = 1
            else:
                i += 1
                j -= 1
        cnt += 1
            
N = 7
matrix = []             # 初始化二维矩阵matrix(二维列表)
for i in range(N):
    matrix.append([])
    for j in range(N):
        matrix[i].append(0)
Helix_MatrixII(N)
prt(matrix)

执行结果:

 四、题目求解算法

题目要求输入矩阵规模n和坐标(i, j)三个参数,求出矩阵(i, j)处的元素值。所以先按n求出矩阵,现按坐标输出元素值。

程序代码如下:

def Helix_MatrixII(n):
    cnt = 1
    i = j = 0
    k = 1
    while True:
        matrix[i][j] = cnt
        if i == n-1 and j == n-1:
            break
        if k == 1:        # 从左下往右上
            if i == 0 :
                j += 1
                if j >= n:
                    j = n-1
                    i = i+1 if i < n -1 else n-1
                k = -1
            elif j == n-1:
                i += 1
                k = -1
            else:
                i -= 1
                j += 1
        else:             # 从右上往左下
            if j == 0 :
                i += 1
                if i >= n:
                    i = n-1
                    j = j+1 if j < n -1 else n-1
                k = 1
            elif i == n-1:
                j += 1
                k = 1
            else:
                i += 1
                j -= 1
        cnt += 1
          
N, x, y = map(int, input().split())
matrix = []               # 初始化二维矩阵matrix(二维列表)
for i in range(N):
    matrix.append([])
    for j in range(N):
        matrix[i].append(0)
Helix_MatrixII(N)
print(matrix[x-1][y-1])

执行结果:

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

【算法题】螺旋矩阵III (求解n阶蛇形矩阵) 的相关文章

随机推荐

  • REQ 【CodeForces - 594D】【树状数组+离线查询+区间思维】

    题目链接 很好的一道题 昨晚上推的 今天由于代码能力太弱敲了半天 再不断的找到自己思维的BUG 于是RE了一发 T了一发 WA了一发 就Ac了 还不错 那我们来讲解一下题目的思路 我们知道对于一个值的欧拉函数值 就是它的值去乘上它所有的质数
  • 自然语言处理实验—分词算法(含python代码及详细例子讲解)

    自然语言处理实验 分词算法 最近在学自然语言处理 这是第一个上机实验自然语言处理的分词算法 也是自然语言处理比较入门的算法 和大家分享一下 首先 自然语言处理 英文是 Nature Language Process 简称 NLP 是人工智能
  • 【PHP教程(二)】php登陆验证(附代码)

    1 登陆脚本 2 受保护的网页示例 3 注销脚本 4 注意事项 5 Hash函数字符串转换 6 php登陆脚本 哈希值验证 可以使用 PHP 创建登录脚本 PHP 提供了用于处理用户身份验证和会话的内置函数和功能 这是登录系统的基本组件 这
  • 2023春节祝福系列第一弹(上)(放飞祈福孔明灯,祝福大家身体健康)(附完整源代码及资源免费下载)

    2023春节祝福系列第一弹 上 放飞祈福孔明灯 祝福大家身体健康 附完整源代码及资源免费下载 目录 一 前言 二 一片星光闪烁的旋转星空 1 效果展示 2 相关源代码 3 语法解释 3 1 线性渐变 linear gradient 3 2
  • Java异常知识点总结

    Java异常知识点总结 1 异常处理机制主要回答了三个问题 What Where Why What 异常类型回答了什么被抛出 Where 异常堆栈跟踪回答了在哪抛出 Why 异常信息回答了为什么被抛出 2 Java异常体系 RuntimeE
  • Python的Object基类__repr__方法

    Python的Object基类 repr 方法 Python基类的內建方法 repr 是执行一个官方的 或者正式的 代表一个对象的字符串 也就是说可以将字符串转换成一个Python对象 如果可能的话 最好是有效的表达式字符串 如果不可能的话
  • Visual Studio 2017 如何更改缓存以及组件的路径,以保证VS2017正常启动

    当安装完Visual Studio 2017时 发现安装过程中设置的缓存路径或组件存放路径不合理 但一旦修改 会导致Visual Studio 2017出现项目加载失败等问题 修改方法是通过 regedit命令打开windows注册表 然后
  • 财务系统软件c语言,用vc++6.0编写一个简单的财务应用程序来计算职工所得的实际工资...

    满意答案 xfitijnf 2014 09 30 采纳率 51 等级 12 已帮助 32118人 又写了一个简单的 c语言 另外 我和一楼不是一个人 123456789101112131415161718192021222324252627
  • Redis为服务器设置密码

    以下以Windows版本为例 在 redis windows service conf 文件 设置 requirepass foobared requirepass 123456 masterauth
  • AD常用使用快捷键和技巧

    PCB布线常使用 ctrl m 测量长度 ctrl C 取消显示测量长度 Q 单位切换 shift ctrl r 取消显示标注 shift S 显示层切换 ctrl 右击 高亮显示一条线 ctrl D PCB 2D显示设置 层 透明度 A
  • OpenCV:imwrite函数保存图片

    imwrite函数功能 用于将图像保存到指定的文件 可以为各种格式的图像 函数原型 bool cv imwrite const String filename InputArray img const std vector
  • js实现input的赋值

    input框赋值 如下所示 是一个文本框的html代码 实际开发中 要涉及到将数据库中的数据取出然后放入input框中
  • UML 用例图、顺序图、状态图、类图、包图、协作图、流程图

    面向对象的问题的处理的关键是建模问题 建模可以把在复杂世界的许多重要的细节给抽象出 许多建模工具封装了UML 也就是Unified Modeling Language 这篇课程的目的是展示出UML的精彩之处 UML中有九种建模的图标 即 用
  • vue事件对象、冒泡、阻止默认行为

    事件对象
  • 【满分】【华为OD机试真题2023 JAVA&JS】任务混部

    华为OD机试真题 2023年度机试题库全覆盖 刷题指南点这里 任务混部 知识点差分 时间限制 1s 空间限制 256MB 限定语言 不限 题目描述 公司创新实验室正在研究如何最小化资源成本 最大化资源利用率 请你设计算法帮他们解决一个任务混
  • sql-labs注入1-10关

    sql labs注入第1 10关 Less 1 输入 id 1登录页面正常 Order by对前面的数据进行排序 这里有三列数据 我们就只能用order by 3 超过3就会报错 order by 4 的结果显示结果超出 爆数据库名 id
  • SpringBoot+MyBatis搭建迷你小程序

    本项目如下 maven的安装目录在哪 setting文件放在哪 仓库在哪 分别为G Program Files x86 apache maven 3 5 4 conf 与G Program Files x86 apache maven 3
  • 【高等代数】行列式的定义和性质

    文章目录 逆序数 逆序数的定义 逆序数的一个重要性质 行列式的定义 行列式的性质 逆序数 逆序数的定义 一个排列中的某两个数字 如果前面的数大于后面的数 那么它们就是一个逆序 一个排列中逆序的总数就称为这个排列的逆序数 逆序数用 j 1
  • JAVA的安装与卸载

    1 java的卸载 1 删除java的安装目录 2 删除系统环境变量里的JAVA HOME和Path里面的bin目录和jre bin目录 3 cmd输入java version 查看是否删除取消 2 java的安装 1 百度搜索jdk1 8
  • 【算法题】螺旋矩阵III (求解n阶蛇形矩阵)

    一 问题的提出 n阶蛇形矩阵的特点是按照图1所示的方式排列元素 n阶蛇形矩阵是指矩阵的大小为n n 其中n为正整数 题目背景 一个 n 行 n 列的螺旋矩阵可由如图1所示的方法生成 观察图片 找出填数规律 填数规则为从 1 开始填到 n n