面试项目算法 - 数桥问题python求解

这篇具有很好参考价值的文章主要介绍了面试项目算法 - 数桥问题python求解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本项目基于一个流行的日本谜题--"Hashiwokakero"、"Hashi "或 "Bridges"。你需要编写一个程序来解决这个谜题,并简要说明你所使用的算法和数据结构。

程序的输入将是一个由数字和点组成的矩形数组,例如:

面试项目算法 - 数桥问题python求解,python,java,前端,算法,面试
每个数字代表一个 "岛屿",而点代表岛屿之间的空隙(水域)。大于 9 的数字用 "a"(10)、"b"(11)或 "c"(12)表示。游戏的目的是用一个桥梁网络连接所有岛屿,同时满足以下规则:

1.所有桥梁必须水平或垂直延伸
2.桥梁不能相互交叉,也不能与其他岛屿交叉
3.连接任何一对岛屿的桥梁不能超过三座
4.连接每个岛屿的桥梁总数必须等于岛上的桥梁数
5.例如,读取上述 10 行输入后,您的程序可能会产生以下输出:

面试项目算法 - 数桥问题python求解,python,java,前端,算法,面试
请注意,单座桥梁用字符"-"或"|"表示,成对桥梁用"="或"""表示,三座桥梁用 "E "或"#"表示,

这取决于它们是横向还是纵向。桥梁和岛屿之间的水域用空格符" '"表示。
在某些情况下,谜题可能有很多解,在这种情况下,您的程序应该只打印一个解。有关谜题的更多详情,请参见维基百科页面。不过请注意,我们的版本允许最多连接 3 个桥,而不是 2 个桥;而且我们并不坚持要求整个图形都是连通的。文章来源地址https://www.toymoban.com/news/detail-841674.html

import sys
import random
direction = [(0, -1), (-1, 0), (0, 1), (1, 0)]
max_bridge_num = 3
ch_to_int = [{0: 0, '-': 1, '=': 2, 'E': 3, '|': 0, '"': 0, '#': 0},
             {0: 0, '|': 1, '"': 2, '#': 3, '-': 0, '=': 0, 'E': 0}]
int_to_ch = [{0: 0, 1: '-', 2: '=', 3: 'E'},
             {0: 0, 1: '|', 2: '"', 3: '#'}]



def scan_map():
    text = []
    for line in sys.stdin:
        row = []
        for ch in line:
            n = ord(ch)
            if n >= 48 and n <= 57:  # between '0' and '9'
                row.append(n - 48)
            elif n >= 97 and n <= 122:  # between 'a' and 'z'
                row.append(n - 87)
            elif ch == '.':
                row.append(0)
        text.append(row)

    return text



def get_bridge_code(dir, ch):
    if isinstance(ch, int) and 0 < ch:
        return 0
    return ch_to_int[dir % 2][ch]


def format(ele):
    if isinstance(ele, int):
        if ele >= 10:
            return chr(ord('a') + ele - 10)
        elif ele == 0:
            return ' '
    return ele



def print_map(data):
    for row in data:
        # print(' '.join(str(format(cell)) for cell in row))
        print(''.join(str(format(cell)) for cell in row))

def map_2_tuple(data):
    return tuple(tuple(row) for row in data)

def is_valid(data, i, j):
    n = len(data)
    m = len(data[0])
    if i >= 0 and i < n and j >= 0 and j < m:
        return True
    return False

def get_bridge_num(data, i, j, dir):
    ni = i + direction[dir][0]
    nj = j + direction[dir][1]
    if not is_valid(data, ni, nj):
        return 0
    return get_bridge_code(dir % 2, data[ni][nj])



def search_direction(data, i, j, dir):
    bnum = get_bridge_num(data, i, j, dir)
    if bnum >= max_bridge_num:
        return [0, (-1,-1)]
    bnch = int_to_ch[dir % 2][bnum]
    ni = i + direction[dir][0]
    nj = j + direction[dir][1]
    while is_valid(data, ni, nj) and data[ni][nj] == bnch:
        ni = ni + direction[dir][0]
        nj = nj + direction[dir][1]
    if not is_valid(data, ni, nj):
        return [0, (-1,-1)]
    if isinstance(data[ni][nj], int) and 0 < data[ni][nj]:
        exsit_bn = 0
        for nd in range(0, 4):
            exsit_bn += get_bridge_num(data, ni, nj, nd)
        return [min(max_bridge_num - bnum, data[ni][nj] - exsit_bn), (ni,nj)]
    return [0, (-1,-1)]

def potential_bridge_num(data, i, j, dir):
    return search_direction(data, i, j, dir)[0]

def add_bridge(data, i, j, dir, num):
    if num == 0:
        return
    #print("bridge",i,j,dir,num)
    bnum = get_bridge_num(data, i, j, dir)
    bnch = int_to_ch[dir % 2][bnum]
    nbnch = int_to_ch[dir % 2][bnum + num]
    ni = i + direction[dir][0]
    nj = j + direction[dir][1]
    while is_valid(data, ni, nj) and data[ni][nj] == bnch:
        data[ni][nj] = nbnch
        ni = ni + direction[dir][0]
        nj = nj + direction[dir][1]

def get_min_comfirmed_bridges(potential, remain_bn):
    sump = sum(potential)
    min_bridge_list = []
    for p in potential:
        min_bridge_list.append(max(0, remain_bn - sump + p))
    return min_bridge_list 

def add_comfirmed_and_check(data, ris):
    n = len(data)
    m = len(data[0])
    correct = True 
    valid = True
    no_comfirmed_bridge = True
    for (i, j) in ris:
        exsit = []
        potential = []
        for d in range(0, 4):
            exsit.append(get_bridge_num(data, i, j, d))
            potential.append(potential_bridge_num(data, i, j, d))
        if sum(potential) + sum(exsit) >= data[i][j]:
            min_bridge = get_min_comfirmed_bridges(potential, data[i][j] - sum(exsit))
            for d in range(0, 4):
                if min_bridge[d] > 0:
                    no_comfirmed_bridge = False
                    add_bridge(data, i, j, d, min_bridge[d])
                    exsit[d] += min_bridge[d] 
                    potential[d] -= min_bridge[d] 
        else:
            valid = False
        if sum(exsit) > data[i][j]:
            valid = False
        elif sum(exsit) < data[i][j]:
            correct = False
        elif sum(exsit) == data[i][j]:
            if (i,j) in ris:
                ris.remove((i,j))
    return [correct, valid, no_comfirmed_bridge] 

def dfs_map(data, i, j, vis2):
    if (i,j) in vis2.keys():
        return 0
    vis2[(i,j)] = True

    ret = data[i][j]
    for d in range(0, 4):
        ret -= get_bridge_num(data, i, j, d)
        [potential, (ni,nj)] = search_direction(data,i,j,d)
        if potential > 0:
            ret += dfs_map(data, ni, nj, vis2)
    if ret < 0:
        print("error")
    return ret


def check_map_right(data, ris):
    dfs_vis = {}
    for (i, j) in ris:
        numsum = dfs_map(data,i, j,dfs_vis)
        if numsum % 2 == 1:
            return False
    return True

def cost_estimation(num, po):
    if (num,po[0],po[1],po[2],po[3]) in est_mp.keys():
        return est_mp[(num,po[0],po[1],po[2],po[3])]
    if num == 0:
        return 0
    count = 0
    for i in range(0,4):
        for k in range(1, po[i]+1):
            if num - k >= 0:
                copied_po = po[:]
                copied_po[i] -= k
                count += cost_estimation(num-k, copied_po) + 1
    est_mp[(num,po[0],po[1],po[2],po[3])] = count
    return count

def heuristic(data, ris):
    res = []
    for (i, j) in ris:
        exsit = []
        potential = []
        for d in range(0, 4):
            exsit.append(get_bridge_num(data, i, j, d))
            potential.append(potential_bridge_num(data, i, j, d))
        if sum(exsit) == data[i][j]:
            continue
        remain = data[i][j]-sum(exsit)
        cost = cost_estimation(remain, potential)
        res.append((i,j,cost))
    #random.shuffle(res)
    #res_xy = [(x[0], x[1]) for x in res]
    #return res_xy
    sorted_res = sorted(res, key=lambda x: x[2])
    sorted_res_xy = [(x[0], x[1]) for x in sorted_res]
    return sorted_res_xy

def backtrack(data, vis, ris):
    if map_2_tuple(data) in vis.keys():
        return False
    vis[map_2_tuple(data)] = True
    while True:
        [correct, valid, no_comfirmed] = add_comfirmed_and_check(data, ris)
        if not valid:
            return False
        if correct:
            print_map(data)
            return True
        if no_comfirmed:
            break
    if not check_map_right(data, ris):
        return False
    #print_map(data)
    #print("--------"+str(len(vis))+"----------")
    ris = heuristic(data, ris)
    for (i, j) in ris:
        dir_list = [0, 1, 2, 3]
        random.shuffle(dir_list)
        for d in dir_list:
            if potential_bridge_num(data, i, j, d) > 0:
                data_tmp = [row[:] for row in data]
                ris_tmp = ris[:]
                add_bridge(data_tmp, i, j, d, 1)
                if backtrack(data_tmp, vis, ris_tmp):
                    return True
    return False


if __name__ == '__main__':
    map = scan_map()
    #print_map(map)
    #print("------------------------")
    vis = {}
    islands = []
    est_mp = {}
    n = len(map)
    m = len(map[0])
    for i in range(0, n):
        for j in range(0, m):
            if isinstance(map[i][j], int) and 0 < map[i][j]:
                islands.append((i,j))
    backtrack(map,vis,islands)

到了这里,关于面试项目算法 - 数桥问题python求解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • A*算法求解迷宫问题(算法讲解与证明、python实现与可视化)

    目录 一、引入 二、具体细节 1、BFS(Breadth First Search) 2、Dijkstra(Uniform Cost Search) 3、启发式(Heuristic search) 4、A*算法 4.1 算法细节 4.2 A与A*算法 4.3 A*算法证明 4.4 算法过程 三、具体实现 1、实验要求 2、代码实现 四、源代码        当我开始学习该算法时,网上已经有了很

    2023年04月08日
    浏览(55)
  • 求解三维装箱问题的启发式深度优先搜索算法(python)

    给定一个容器(其体积为 V V V ) 和一系列待装载的箱子,容器和箱子的形状都是长方体。问题的目标是要确定一个可行的箱子放置方案使得在满足给定装载约束的情况下,容器中包含的箱子总体积 S S S 尽可能的大,即填充率尽可能的大,这里填充率指的是 S / V ∗ 100 % S/ V * 1

    2024年02月05日
    浏览(101)
  • 数学建模|通过模拟退火算法求解供货与选址问题:问题二(python代码实现)

    今天继续用模拟退火算法供货与选址问题的问题二,如果还没看过问题一的可以看我之前的博客 数学建模|通过模拟退火算法求解供应与选址问题:问题一(python代码实现)-CSDN博客 这里还是把题目放上来(题目来自数学建模老哥的视频): 那么我们可以分析一下,第一问和

    2024年01月16日
    浏览(57)
  • 【运筹优化】ALNS自适应大领域搜索算法求解TSP问题 + Java代码实现

    旅行推销员问题(TSP)提出以下问题:“给定 n n n 个城市的列表,其中有一个起始城市,以及每对城市之间的距离,访问每个城市一次并返回起始城市的最短可能路线是什么?”。 这又是一个重要的NP-hard组合优化,特别是在运筹学和理论计算机科学领域。这个问题最早是在1

    2024年02月13日
    浏览(51)
  • 【运筹优化】网络最大流问题及三种求解算法详解 + Python代码实现

    标题中时间复杂度用到的 符号说明 :f 代表最大流的大小,m代表边的数量,n 代表节点的数量 本博客学习自:B站-ShusenWang 最大流问题,是网络流理论研究的一个基本问题,求网络中一个可行流 f ∗ f* f ∗ ,使其流量 v ( f ) v(f) v ( f ) 达到最大, 这种流 f f f 称为最大流,这个

    2024年02月02日
    浏览(57)
  • python实现Dijkstra算法求解最短路径问题(Shortest Path Problem)

    最短路问题(Shortest Path Problem,SPP)是 图论 的一个经典问题,其目的在于寻找网络中任意两个节点间的最短路径,这里的最短可以衍生为距离最短、费用最小、时间最短等一系列度量。当前的涌现了很多最短路径的变种,如带资源约束的最短路径问题(Shortest Path Problem wit

    2024年02月09日
    浏览(43)
  • 【运筹优化】拉格朗日松弛 & 次梯度算法求解整数规划问题 + Java调用Cplex实战

    当遇到一些很难求解的模型,但又不需要去求解它的精确解,只需要给出一个次优解或者解的上下界,这时便可以考虑采用松弛模型的方法加以求解。 对于一个整数规划问题,拉格朗日松弛放松模型中的部分约束。这些被松弛的约束并不是被完全去掉,而是利用拉格朗日乘子

    2024年02月11日
    浏览(50)
  • 关于旅行商问题的多种算法求解

    一、问题描述 旅行商问题是指旅行家要旅行n个城市,要求每个城市经历一次且仅经历一次然后回到出发城市,并要求所走路程最短。 首先通过所给出的一个无向图,即n个顶点,m个无向边,每条边有一个权值代表两个点之间的距离,要求把每一个点都走一遍并回到原点,求

    2024年02月04日
    浏览(50)
  • 遗传算法及基于该算法的典型问题的求解实践

        遗传算法是一个很有用的工具,它可以帮我们解决生活和科研中的诸多问题。最近在看波束形成相关内容时了解到可以用这个算法来优化阵元激励以压低旁瓣,于是特地了解和学习了一下这个算法,觉得蛮有意思的,于是把这两天关于该算法的学习和实践的内容总结成了

    2024年03月21日
    浏览(49)
  • 【多目标规划问题求解】ε-约束算法

    TIME:2022/07/30 Author:雾雨霜星 Web:雾雨霜星的小站 小站原文链接:https://www.shuangxing.top/#/post?id=27 [1]Nima Amjady and Jamshid Aghaei and Heidar Ali Shayanfar. Stochastic Multiobjective Market Clearing of Joint Energy and Reserves Auctions Ensuring Power System Security[J]. IEEE Transactions on Power Systems, 2009, 24(4) : 1841-1854. [

    2024年02月05日
    浏览(173)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包