CodeIQ の「迷路」問題の僕の回答
CodeIQ の迷路問題 の僕の回答。
sqlite3 に node と edge のテーブル作ってグラフの最短経路問題として解いています。
超スタンダードな解き方。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sqlite3
def main():
try:
conn = sqlite3.connect(':memory:')
# conn = sqlite3.connect('testDB')
strSQL = '''
CREATE TABLE node(
node TEXT CONSTRAINT pk_node PRIMARY KEY
, dist integer);
--WITH N(n) AS (
-- SELECT UNICODE('0')
-- UNION ALL SELECT n + 1 FROM N WHERE n < UNICODE('9'))
-- INSERT INTO node(node) SELECT char(n) FROM N;
--WITH N(n) as (
-- SELECT UNICODE('A')
-- UNION ALL SELECT n + 1 FROM N WHERE n < UNICODE('Z'))
-- INSERT INTO node(node) SELECT char(n) FROM N;
CREATE TABLE edge(
node1 TEXT
, node2 TEXT
, CONSTRAINT pk_edge PRIMARY KEY(
node1
, node2));
INSERT INTO edge
VALUES
('0','6')
, ('1','2')
, ('2','3')
, ('2','8')
, ('3','4')
, ('4','5')
, ('4','A')
, ('6','7')
, ('7','8')
, ('9','A')
, ('9','F')
, ('A','G')
, ('B','H')
, ('C','D')
, ('D','J')
, ('E','K')
, ('H','N')
, ('I','J')
, ('I','O')
, ('J','K')
, ('J','P')
, ('K','L')
, ('M','N')
, ('M','S')
, ('N','T')
, ('O','U')
, ('Q','R')
, ('Q','W')
, ('R','S')
, ('T','Z')
, ('U','V')
, ('V','W')
, ('X','Y')
, ('Y','Z')
;
INSERT INTO edge(node1, node2)
SELECT
node2, node1
FROM
edge
--WHERE
-- node1 < node2
;
'''
conn.executescript(strSQL)
strInput = input()
opengate = strInput[0]
strStart = strInput[1]
strend = strInput[2]
strSQL = '''
INSERT INTO edge VALUES (:node1,:node2),(:node2,:node1)
'''
if opengate == 'a':
conn.execute(strSQL, {'node1': '7', 'node2': 'D'})
elif opengate == 'b':
conn.execute(strSQL, {'node1': 'E', 'node2': 'F'})
elif opengate == 'c':
conn.execute(strSQL, {'node1': 'G', 'node2': 'M'})
elif opengate == 'd':
conn.execute(strSQL, {'node1': 'A', 'node2': 'B'})
strSQL = '''
INSERT INTO node VALUES(?, 0);
'''
conn.execute(strSQL, (strStart,))
strSQL_AddNode = '''
INSERT INTO node
SELECT
node2, nS.dist + 1
FROM
edge
INNER JOIN node nS
ON edge.node1 = nS.node
LEFT OUTER JOIN node nE
ON edge.node2 = nE.node
WHERE
nE.node is null;
'''
strSQL_GetDistance = '''
SELECT
dist
FROM
node
WHERE
node.node = ?
'''
cur = conn.cursor()
while(True):
conn.execute(strSQL_AddNode)
rows = cur.execute(strSQL_GetDistance, (strend,)).fetchall()
if len(rows) > 0:
break
print(rows[0][0])
finally:
# conn.commit()
conn.close()
if __name__ == '__main__':
main()
Author And Source
この問題について(CodeIQ の「迷路」問題の僕の回答), 我々は、より多くの情報をここで見つけました https://qiita.com/KAZAMAI_NaruTo/items/67879c753b249db29253著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .