Hatena::ブログ(Diary)

xmallocのプログラミングノート

2010年01月11日

例の問題解いてみた

はてブで話題になってたので、人材獲得作戦・4 試験問題ほかを解いてみた。

import sys

fh = open(sys.argv[1])
map = []
goal = start = None

xlen = ylen = 0
y = 0
for line in fh:
    arr = []
    x = 0
    for ch in line[:len(line)-1]:
        arr.append({ 'c':ch, 'n':-1, 'l':False })
        if ch == 'S':
            start = (x, y)
        if ch == 'G':
            goal = (x, y)
        x += 1
    if xlen == 0:
        xlen = x
    y += 1
    map.append(arr)
fh.close()

ylen = len(map)

def printmap():
    for y in map:
        line = ''
        for x in y:
            line += x['c']
        print line

queue = [(start[0], start[1], 0)]
while queue:
    x, y, step = queue.pop()
    map[y][x]['l'] = True
    map[y][x]['n'] = step

    step += 1
    for _x, _y in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
        if (_x < 0 or _x >= xlen or _y < 0 or _y >= ylen or
            map[_y][_x]['c'] != ' '):
            continue
        if not map[_y][_x]['l'] or map[_y][_x]['n'] > step:
            queue.append((_x, _y, step))

x, y = goal
while map[y][x]['c'] != 'S':
    nx, ny = (0, 0)
    n = -1
    for _x, _y in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
        if (_x < 0 or _x >= xlen or _y < 0 or _y >= ylen or
            map[_y][_x]['c'] == '*'):
            continue
        if n == -1 or map[_y][_x]['n'] < n:
            n = map[_y][_x]['n']
            nx, ny = (_x, _y)
    x, y = nx, ny
    if map[y][x]['c'] == ' ':
        map[y][x]['c'] = '$'

printmap()

自分でも笑っちゃうぐらい超グダグダなコードだけど、3時間で解けって話なので実際に解いたときのソースそのまま貼っとく。

実行結果はこんな感じ。(空白崩れてるような気がするけど、はてなの使い方がいまいち分からんのでとりあえず放置。公開したら直ってましたw)

**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

解くまでにかかった時間はだいたい1時間35分ぐらい、秒までは計ってない。


までもとりあえず、この問題解けなくても俺の仕事には何の支障も無いよww*1

*1:これを言いたかったので解いただけ。解いた人間が言うんだから多少は信憑性あるんじゃね?www

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/xmalloc/20100111/1263230882