GDD 2011 スライドパズル祭り
とりあえず解ける段階まで作ってそのまま放置してしまったコードをとりあえずぺたり。ヽ( ・∀・)ノ● ウンコードウンコードー
ただの幅優先探索でメモリ食い過ぎて死にます。チキンなので問題の面積指定して解かせます。あぁもう恥ずかしい
# -*- coding: utf-8 -*- from copy import deepcopy import sys size = 1 class AnswerFound(Exception): def __init__(self, answer): self.answer = answer def log(line): f = open('log%d.txt' % size, 'a') try: f.write(line + "\n") finally: f.close() def write_answer(id, answer): print id, ":", answer f = open('answer%d.txt' % size, 'a') try: f.write('%d: %s\n' % (id, answer)) finally: f.close() def make_goal(line): s = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0" s = s[:len(line) - 1] try: for i in xrange(len(line) - 1): if line[i] == '=': s = s.replace(s[i], '=') s += '0' return s except: log(line) raise class Board(object): def read(self): w, h, b = [x for x in raw_input().split(',')] w = int(w) h = int(h) self.b = [list(b[i*w : (i+1)*w]) for i in xrange(h)] self.w = w self.h = h self.space = self.find_space() self.history = '' def solve(self): state_map = {} queue = [self] goal = make_goal(self.board_str()) log("START: " + self.board_str()) log("GOAL: " + goal) try: for i in xrange(1000000): board = queue.pop(0) #log("Iteration #%d" % i) #print board.board_str(), board.history #print board #print "------------" move_results = (board.go_left(), board.go_up(), board.go_right(), board.go_down()) for r in move_results: if not r: continue if r.board_str() in state_map: continue if r.board_str() == goal: raise AnswerFound(r.history) queue.append(r) state_map[r.board_str()] = r except AnswerFound, e: return e.answer def get_by_space(self, dx, dy): """return char near space""" return self.b[self.space[1] + dy][self.space[0] + dx] def set_by_space(self, dx, dy, value): """set char near space""" self.b[self.space[1] + dy][self.space[0] + dx] = value def swap_space(self, dx, dy, dirchar): """return new board object that the space is swapped with target (space.x + dx, space.y, dy). if the target is '=', return None.""" if self.get_by_space(dx, dy) == '=': return None that = deepcopy(self) that.set_by_space(0, 0, that.get_by_space(dx, dy)) that.set_by_space(dx, dy, '0') that.space = (that.space[0] + dx, that.space[1] + dy) that.history += dirchar return that def go_left(self): if self.space[0] == 0: return None if len(self.history) > 0 and self.history[-1] == 'R': return None return self.swap_space(-1, 0, 'L') def go_up(self): if self.space[1] == 0: return None if len(self.history) > 0 and self.history[-1] == 'D': return None return self.swap_space(0, -1, 'U') def go_right(self): if self.space[0] >= self.w - 1: return None if len(self.history) > 0 and self.history[-1] == 'L': return None return self.swap_space(1, 0, 'R') def go_down(self): if self.space[1] >= self.h - 1: return None if len(self.history) > 0 and self.history[-1] == 'U': return None return self.swap_space(0, 1, 'D') def to_lines(self): return (''.join(s) for s in self.b) def board_str(self): return ''.join(self.to_lines()) def __str__(self): return '\n'.join(self.to_lines()) + '\n' + self.history def find_space(self): """returns (x,y)""" for y in xrange(self.h): for x in xrange(self.w): if self.b[y][x] == '0': return (x, y) class Solver(object): def solve_all(self): self.LX, self.RX, self.UX, self.DX = [ int(x) for x in raw_input().split(' ')] N = int(raw_input()) boards = [] for i in xrange(N): boards.append(Board()) boards[i].read() boards[i].id = i for b in boards: if b.w * b.h == size: answer = b.solve() write_answer(b.id, answer) size = int(sys.argv[1]) s = Solver() s.solve_all()