我必须写一个函数交叉,鉴于 国家名和n
(步期望的数量)为您提供了一套国家 我可以达到穿越从特定国家原料N-国家。Python的规划行程 - 唯一路径
需要注意的是:
- 零个步骤,你无法从国家开始退出;
- 在一步你只能在边境国家获得;
- 路径必须是最小的,例如从意大利你可以在比利时穿越瑞士 和德国或者只有法国第二个是可以选择的;
- 您无法跨越一个国家两次或多次返回,例如意大利→瑞士→意大利 或意大利→瑞士→法国错误。
这是我的地图:
neighborhood = {
'albania': ['greece', 'macedonia', 'serbia', 'montenegro'],
'andorra': ['spain', 'france'],
'austria': ['liechtenstein', 'switzerland', 'italy',
'czech republic', 'germany', 'slovakia',
'hungary', 'slovenia'],
'belarus': ['russia', 'lithuania', 'latvia', 'poland',
'ukraine'],
'belgium': ['luxembourg', 'germany', 'france', 'netherlands'],
'bosnia and herzegovina': ['montenegro', 'serbia', 'croatia'],
'bulgaria': ['romania', 'serbia', 'macedonia', 'greece'],
'croatia': ['bosnia and herzegovina', 'serbia', 'hungary',
'slovenia'],
'czech republic': ['slovakia', 'austria', 'germany', 'poland'],
'denmark': ['germany'],
'estonia': ['russia', 'latvia'],
'finland': ['sweden', 'russia', 'norway'],
'france': ['spain', 'andorra', 'monaco', 'luxembourg',
'belgium', 'germany', 'switzerland', 'italy'],
'germany': ['denmark', 'luxembourg', 'belgium', 'france',
'netherlands', 'poland', 'czech republic',
'austria', 'switzerland'],
'greece': ['bulgaria', 'macedonia', 'albania'],
'hungary': ['romania', 'ukraine', 'slovakia', 'austria',
'slovenia', 'croatia', 'serbia'],
'iceland': [],
'ireland': ['united kingdom'],
'italy': ['france', 'switzerland', 'austria', 'slovenia',
'san marino', 'vatican city'],
'latvia': ['russia', 'estonia', 'lithuania', 'belarus'],
'liechtenstein': ['austria', 'switzerland'],
'lithuania': ['russia', 'latvia', 'belarus', 'poland'],
'luxembourg': ['belgium', 'germany', 'france'],
'macedonia': ['bulgaria', 'serbia', 'albania', 'greece'],
'malta': [],
'moldova': ['ukraine', 'romania'],
'monaco': ['france'],
'montenegro': ['albania', 'serbia', 'bosnia and herzegovina'],
'netherlands': ['germany', 'belgium'],
'norway': ['sweden', 'finland', 'russia'],
'poland': ['russia', 'lithuania', 'belarus', 'ukraine',
'slovakia', 'czech republic', 'germany'],
'portugal': ['spain'],
'romania': ['ukraine', 'moldova', 'bulgaria', 'serbia',
'hungary'],
'russia': ['norway', 'finland', 'estonia', 'latvia',
'lithuania', 'belarus', 'ukraine', 'poland'],
'san marino': ['italy'],
'serbia': ['bosnia and herzegovina', 'hungary', 'croatia',
'montenegro', 'albania', 'macedonia', 'bulgaria',
'romania'],
'slovakia': ['hungary', 'austria', 'czech republic', 'poland',
'ukraine'],
'slovenia': ['italy', 'austria', 'hungary', 'croatia'],
'spain': ['portugal', 'andorra', 'france'],
'sweden': ['norway', 'finland'],
'switzerland': ['germany', 'france', 'liechtenstein', 'austria',
'italy'],
'ukraine': ['russia', 'belarus', 'poland', 'moldova',
'slovakia', 'hungary', 'romania'],
'united kingdom': ['ireland'],
'vatican city': ['italy']
}
测试主要是:
if __name__ == '__main__':
print("*** From Italy in ")
for steps in range(0,8):
print("[{0}] = {1}".format(steps, crossing("italy", steps)))
print("*** From Sweden in [5] steps, you get in", crossing('sweden', 5))
print("*** From Germany in [2] steps, you get in", crossing('germany', 2))
print("*** From Iceland in [3] steps, you get in", crossing('iceland', 3))
和该执行:
*** From Italy in
[0] = {'italy'}
[1] = {'san marino', 'france', 'slovenia', 'austria', 'switzerland', 'vatican city'}
[2] = {'czech republic', 'hungary', 'luxembourg', 'andorra', 'liechtenstein', 'croatia', 'monaco', 'belgium', 'slovakia', 'germany', 'spain'}
[3] = {'ukraine', 'romania', 'netherlands', 'portugal', 'denmark', 'poland', 'serbia', 'bosnia and herzegovina'}
[4] = {'belarus', 'montenegro', 'lithuania', 'macedonia', 'moldova', 'albania', 'russia', 'bulgaria'}
[5] = {'finland', 'norway', 'latvia', 'estonia', 'greece'}
[6] = {'sweden'}
[7] = set()
*** From Sweden in [5] steps, you get in {'netherlands', 'denmark', 'serbia', 'luxembourg', 'france', 'slovenia', 'austria', 'croatia', 'belgium', 'switzerland', 'bulgaria'}
*** From Germany in [2] steps, you get in {'ukraine', 'belarus', 'italy', 'lithuania', 'andorra', 'slovenia', 'liechtenstein', 'slovakia', 'monaco', 'hungary', 'russia', 'spain'}
*** From Iceland in [3] steps, you get in set()
任何人有一些建议吗?
我试着写:
def crossing(naz,step):
vicini = border(naz)
for i in range(step):
next(vicini)
return next(vicini)
def border(naz):
vicini = set([naz])
yield vicini
yield neighborhood[naz]
你的一些“问题”并不真正构成_问题。这不是一个家庭作业导师网站 – kaveman
创建一个国家及其边界的无向图。那么这只是一个遍历问题。 –
创建无向图并进行(深度) - 首先搜索到深度'n'。 –