<算法>蛇形矩阵求解

蛇形矩阵

右下,下左,左上,上右,循环往复~

解题思路:

  • 在单步前进过程中, x与y, 只能有一个发生变化
  • 每次转向, x与y会发生切换
  • 切换后, x 与 y 都与上次的 方向相反( 第一步: x 增加, x到极限后切换到y; 第二步: y开始增加, y到极限后切换到x; 第三步: x减小(与上次相反), 到极限后切换到y; 第四步: y减小(与上次相反),到极限后切换到x; 如此循环往复)
  • 实现思路就是, 设置一个x,y切换的变量, 变量只有0和1两种状态, 当一个到极限后,切换到另一个, x和y也应该各自设置一个变量, 负责记录x和y上次的极限值是达到了最大值还是最小值!

确定极限值的 优化思路:

如果每次循环都计算x, y当前的极限值会很耗费性能, 不如让x和y直接越界,当越界的点不存在时,再回退一步,并按照"对方"上次的极限值(最大或最小),去确定"正确的转向方向(左或右)

import time
import sys
"""
# x变化或y变化
x和y只能有一个工作(0为x工作, 1为y工作, 初始为1)
x_y_work = 1

设置状态 add_or_cut:
第一位控制x: 0为增加, 1为减小
第二位控制y: 0为增加, 1为减小
初始为:[0, 0]
"""
# 尝试移除坐标,成功则返回0,移除失败, 则返回1
def remove_atom(x_y_list, snake_node, result_list):
    # time.sleep(1)
    if snake_node in x_y_list:
        x_y_list.remove(snake_node)
        result_list.append(snake_node)
        print(snake_node)
        print("剩余元素",len(x_y_list),"个!")
        return 0
    else:
        return 1

# 将二维列表转换为实际的数字位置
def l_to_num(N, result_list):

    for n in range(len(result_list)):
        result_list[n] = result_list[n][0] * N + result_list[n][1] + 1
    return result_list

def main():
    # 确定边长
    N = input("请输入边长:")

    try:
        N = int(N)
    except Exception as e:
        print("输入的必须为整数,请重新输入!")
        sys.exit()

    # 决定x或y工作
    x_y_work = 1

    # 决定x或y加还是减, 0为加, 1为减

    add_or_cut = [0, 0]

    # 当前所在的位置
    source_x = 0
    source_y = 0
    x_y_list = [[x,y] for x in range(N) for y in range(N)]
    result_list = list()

    print("原始的地图为:")
    for m in range(N):
        for n in range(N):
            print(x_y_list[m+n],end=",")
        print("")

    # 开始移动

    while len(x_y_list) != 0:
        print("开始一次循环")

        # 对y进行操作
        if x_y_work == 1:
            # 获取当前坐标
            snake_node = [source_x, source_y]
            # 尝试移除坐标
            sign = remove_atom(x_y_list, snake_node, result_list)
            # 正常删除
            if sign == 0:
                if add_or_cut[1] == 0:
                    source_y += 1
                elif add_or_cut[1] == 1:
                    source_y -= 1
                else:
                    pass

                pass
            # 删除失败,倒车,转向,走一步(但不要删),并切换到 x
            elif sign == 1:
                # 倒车
                if add_or_cut[1] == 0:
                    source_y -= 1
                elif add_or_cut[1] == 1:
                    source_y += 1

                # 判断x当前的状态,确定转向方向
                # 如果x为零,说明下一步要增加了
                if add_or_cut[0] == 0:
                    source_x += 1
                elif add_or_cut[0] == 1:
                    source_x -= 1
                else:
                    print("照理说,不应该到这里")

                # 处理好自己的后事(确定下一步的_加或减的_方向)
                if add_or_cut[1] == 0:
                    add_or_cut[1] = 1
                elif add_or_cut[1] == 1:
                    add_or_cut[1] = 0

                print("切换引擎前的点为:", [source_x, source_y])

                # 正式切换引擎

                x_y_work = 0

            else:
                print("照理说,不应该到这里")
                pass

        # 再对x进行操作
        elif x_y_work == 0:
            # 获取当前坐标
            snake_node = [source_x, source_y]
            # 尝试移除坐标
            sign = remove_atom(x_y_list, snake_node, result_list)

            # 正常删除
            if sign == 0:
                if add_or_cut[0] == 0:
                    source_x += 1
                elif add_or_cut[0] == 1:
                    source_x -= 1
                else:
                    pass

                pass
            # 删除失败,倒车,转向,走一步(但不要删),并切换到 x
            elif sign == 1:
                # 倒车
                if add_or_cut[0] == 0:
                    source_x -= 1
                elif add_or_cut[0] == 1:
                    source_x += 1

                # 判断y当前的状态,确定转向方向
                # 如果y指向为零,说明下一步要增加了
                if add_or_cut[1] == 0:
                    source_y += 1
                elif add_or_cut[1] == 1:
                    source_y -= 1
                else:
                    print("禁区")
                    pass
                # 处理好自己的后事(确定下一步的_加或减的_方向)
                if add_or_cut[0] == 0:
                    add_or_cut[0] = 1
                elif add_or_cut[0] == 1:
                    add_or_cut[0] = 0

                # 正式切换引擎
                x_y_work = 1


            else:
                print("照理说,不应该到这里")
                pass


    result_list = l_to_num(N, result_list)
    print("在二维坐标系中,走过的路径为:")
    print(result_list)

    print("实际走过的位置坐标为:")
    for m in range(N):
        for n in range(N):
            print(result_list[m*N+n],end=",")
        print("")

if __name__ == '__main__':
    main()

原始数据

运行结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1010 过河卒

1010 过河卒 2002年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果...

28950
来自专栏新智元

手把手教你如何用Julia做GPU编程(附代码)

GPU是一个大规模并行处理器,具有几千个并行处理单元。 例如,本文中使用的Tesla k80提供4992个并行CUDA内核。 GPU在频率,延迟和硬件功能方面与...

35710
来自专栏数据结构与算法

BZOJ4006: [JLOI2015]管道连接(斯坦纳树,状压DP)

19810
来自专栏大数据文摘

干货 | 男朋友老是说自己R语言很6,快来用这40道题目检测他

21540
来自专栏CSDN技术头条

使用hadoop进行大规模数据的全局排序

1. Hellow hadoop~~! Hadoop(某人儿子的一只虚拟大象的名字)是一个复杂到极致,又简单到极致的东西。 说它复杂,是因为一个hadoop...

35650
来自专栏崔庆才的专栏

跟繁琐的模型说拜拜!深度学习脚手架 ModelZoo 来袭!

好多天没有更新原创文章了,国庆前的一段时间确实比较忙,整个九月在参加各种面试,另外还有公司的项目,还有自己的毕设,另外还需要准备参加一些活动和讲座,时间排的很紧...

28220
来自专栏深度学习之tensorflow实战篇

Python信贷数据处理与初步分析(ZIP解压)

#!/usr/bin/python # coding=utf-8 ''' @author: lenovo @software: 3.6 PyChar...

41570
来自专栏青玉伏案

算法与数据结构(八) AOV网的关键路径(Swift版)

上篇博客我们介绍了AOV网的拓扑序列,请参考《数据结构(七) AOV网的拓扑排序(Swift面向对象版)》。拓扑序列中包括项目的每个结点,沿着拓扑序列将项目进行...

23280
来自专栏深度学习与数据挖掘实战

干货|PyTorch实用代码段集锦

Facebook公司开源的深度学习框架PyTorch越来越火,PyTorch易于上手。本文节选github中PyTorch的常用实用代码片段,供大...

33570
来自专栏人工智能LeadAI

PyTorch实现自由的数据读取

很多前人曾说过,深度学习好比炼丹,框架就是丹炉,网络结构及算法就是单方,而数据集则是原材料,为了能够炼好丹,首先需要一个使用称手的丹炉,同时也要有好的单方和原材...

66970

扫码关注云+社区

领取腾讯云代金券