Problem:


氷の迷路

四角のマスを縦横にならべた長方形の迷路があります。この迷路では東西南北の隣接するマスへ移動しながら、スタートのマスSを出発し、ゴールのマスGを目指します。マスの種類には、平原、山、氷の３種類があります。SとGは、平原のマスに置かれています。平原のマスには移動できますが、山のマスには移動できません。氷のマスは移動できますが、条件によって氷が割れ動けなくなります。

 氷のマスは東西南北に隣接するもの全体でひとつの塊として扱われます。

 氷の塊のなかで、マスの個数の半分より多くのマスに移動すると、塊全体が割れます。

例えば、図１は与えられた迷路の最短経路のステップ数が 11 であることを示しています。

図1

しかし、図２のように氷のマスを通って近道をしようとすると、大きさが６の氷の塊に対する４回目の移動後に動けなくなってしまいGには到達できません。

図2

このような迷路の情報を入力とし、SからGまでの最短経路のステップ数を求めるプログラムを作成してください。マスの種類はそれぞれ以下の文字で表されます：

文字（半角）
マスの種類

. （ピリオド）
平原

#（シャープ）
山

X
氷

与えられる迷路は必ず解けるものとします。迷路はその東西方向のマスの数 X、南北方向のマスの数 Y と X &times; Y 個の文字として与えられます。

入力

複数のデータセットが与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

X Y
line1
line2
:
lineY

1行目に迷路の大きさを表す整数 X, Y (2 ≤ X, Y ≤ 12) が与えられます。続く Y 行に迷路の i 行目の情報 linei (長さ X の半角英文字列) が与えられます。

データセットの数は 40 を超えない。

出力

データセットごとに、最小のステップ数を１行に出力します。

入力例

5 5
.X.S.
.X#..
.XX##
.#XG.
..X..
7 3
SXX.XXG
X.#.#X.
XXX.XX#
4 4
S...
X.X.
GX..
...X
10 10
..XXXXX.XX
.X.#.#X.XX
SX.#X.X..X
#X.##.X.XX
..XXXX#.XX
##.##.##XX
....X.XX#X
.##X..#X#X
....XX#..X
...#XXG..X
0 0

出力例

11
10
10
33



Sample input:
5 5
.X.S.
.X#..
.XX##
.#XG.
..X..
7 3
SXX.XXG
X.#.#X.
XXX.XX#
4 4
S...
X.X.
GX..
...X
10 10
..XXXXX.XX
.X.#.#X.XX
SX.#X.X..X
#X.##.X.XX
..XXXX#.XX
##.##.##XX
....X.XX#X
.##X..#X#X
....XX#..X
...#XXG..X
0 0


Sample output:
11
10
10
33

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
import collections as co

class Vec(co.namedtuple('Vec','x y')):
    def __add__(self,v):
        return Vec(self.x+v.x, self.y+v.y)

while True:
    X,Y = map(int, input().split())
    if X==0: break
    field = dict()
    ices = set()
    for y in range(Y):
        line = input()
        for x in range(X):
            if line[x] != '#': field[Vec(x,y)] = line[x]
            if line[x] == 'S': startv = Vec(x,y)
            if line[x] == 'G': goalv = Vec(x,y)
            if line[x] == 'X': ices.add(Vec(x,y))
    pairs = [(1,0),(0,1),(-1,0),(0,-1)]
    direcs = [Vec(*pair) for pair in pairs]

    def neighbors(v):
        return {v+direc for direc in direcs if v+direc in field}

    def dfsIce(v0,visited=None):
        if visited==None:
            visited = set()
        visited.add(v0)
        for v in ices & (neighbors(v0) - visited):
            dfsIce(v,visited)
        return visited

    iceAreas = [] # list of sets
    for v in ices:
        flatten = set(it.chain(*iceAreas))
        if v not in flatten:
            iceAreas.append(dfsIce(v))
    # print(iceAreas)

    def testIce(path):
        for area in iceAreas:
            afterArea = area-set(path)
            if len(afterArea) < len(area) / 2:
                return False
        return True

    def bfsPaths(startv, goalv):
        pathQueue = [[startv]]
        while pathQueue:
            path = pathQueue.pop(0)
            v0 = path[-1]
            for v in neighbors(v0) - set(path):
                if v == goalv:
                    return path+[v]
                elif field[v]!='X' or testIce(path+[v]):
                    pathQueue.append(path+[v])

    sp = bfsPaths(startv, goalv)
    print(len(sp)-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
import collections as co

class Vec(co.namedtuple('Vec','x y')):
    __slots__ = ()
    def __add__(self,v):
        return Vec(self.x+v.x, self.y+v.y)

while True:
    X,Y = map(int, input().split())
    if X==0: break
    field = dict()
    ices = set()
    for y in range(Y):
        line = input()
        for x in range(X):
            if line[x] != '#': field[Vec(x,y)] = line[x]
            if line[x] == 'S': startv = Vec(x,y)
            if line[x] == 'G': goalv = Vec(x,y)
            if line[x] == 'X': ices.add(Vec(x,y))
    pairs = [(1,0),(0,1),(-1,0),(0,-1)]
    direcs = [Vec(*pair) for pair in pairs]

    def neighbors(v):
        return {v+direc for direc in direcs if v+direc in field}

    def dfsIce(v0,visited=None):
        if visited==None:
            visited = set()
        visited.add(v0)
        for v in ices & (neighbors(v0) - visited):
            dfsIce(v,visited)
        return visited

    iceAreas = [] # list of sets
    for v in ices:
        flatten = set(it.chain(*iceAreas))
        if v not in flatten:
            iceAreas.append(dfsIce(v))

    areaOf = dict()
    for v in ices:
        for area in iceAreas:
            if v in area:
                areaOf[v] = area
                break

    def testIce(path):
        v = path[-1]
        afterArea = areaOf[v]-set(path)
        return False if len(afterArea) < len(areaOf[v]) / 2 else True

    def bfsPaths(startv, goalv):
        pathQueue = [[startv]]
        while pathQueue:
            path = pathQueue.pop(0)
            v0 = path[-1]
            for v in neighbors(v0) - set(path):
                if v == goalv:
                    return path+[v]
                elif field[v]!='X' or testIce(path+[v]):
                    pathQueue.append(path+[v])
                # else:
                #     pathQueue.append(path+[v])

    sp = bfsPaths(startv, goalv)
    print(len(sp)-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
import collections as co

class Vec(co.namedtuple('Vec','x y')):
    __slots__ = ()
    def __add__(self,v):
        return Vec(self.x+v.x, self.y+v.y)

while True:
    X,Y = map(int, input().split())
    if X==0: break
    field = dict()
    neighbors = dict()
    ices = set()
    for y in range(Y):
        line = input()
        for x in range(X):
            if line[x] != '#': field[Vec(x,y)] = line[x]
            if line[x] == 'S': startv = Vec(x,y)
            if line[x] == 'G': goalv = Vec(x,y)
            if line[x] == 'X': ices.add(Vec(x,y))

    pairs = [(1,0),(0,1),(-1,0),(0,-1)]
    direcs = [Vec(*pair) for pair in pairs]

    for k,v in field.items():
        for direc in direcs:
            neighbors[k] = {k+direc for direc in direcs if k+direc in field}

    def dfsIce(v0,visited=None):
        if visited==None:
            visited = set()
        visited.add(v0)
        for v in ices & (neighbors[v0] - visited):
            dfsIce(v,visited)
        return visited

    iceAreas = [] # list of sets
    for v in ices:
        flatten = set(it.chain(*iceAreas))
        if v not in flatten:
            iceAreas.append(dfsIce(v))
    # print(iceAreas)
    # print()

    areaOf = dict()
    for v in ices:
        for area in iceAreas:
            if v in area:
                areaOf[v] = area
                break

    def testIce(path):
        v = path[-1]
        afterArea = areaOf[v]-set(path)
        return False if len(afterArea) < len(areaOf[v]) / 2 else True

    def bfsPaths(startv, goalv):
        pathQueue = [[startv]]
        while pathQueue:
            path = pathQueue.pop(0)
            v0 = path[-1]
            for v in neighbors[v0] - set(path):
                if v == goalv:
                    return path+[v]
                elif field[v]!='X' or testIce(path+[v]):
                    pathQueue.append(path+[v])

    sp = bfsPaths(startv, goalv)
    print(len(sp)-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
import collections as co

class Vec(co.namedtuple('Vec','x y')):
    __slots__ = ()
    def __add__(self,v):
        return Vec(self.x+v.x, self.y+v.y)

while True:
    X,Y = map(int, input().split())
    if X==0: break
    field = dict()
    neighbors = dict()
    ices = set()
    for y in range(Y):
        line = input()
        for x in range(X):
            if line[x] != '#': field[Vec(x,y)] = line[x]
            if line[x] == 'S': startv = Vec(x,y)
            if line[x] == 'G': goalv = Vec(x,y)
            if line[x] == 'X': ices.add(Vec(x,y))

    pairs = [(1,0),(0,1),(-1,0),(0,-1)]
    direcs = [Vec(*pair) for pair in pairs]
    def getNeighbors(v):
        return {v+direc for direc in direcs if v+direc in field}

    # remove single ice from field and ices
    for ice in ices.copy():
        if getNeighbors(ice).isdisjoint(ices):
            field.pop(ice)
            ices.remove(ice)

    # init neighbors
    for v in field.keys():
        neighbors[v] = getNeighbors(v)

    def dfsIce(v0,visited=None):
        if visited==None:
            visited = set()
        visited.add(v0)
        for v in ices & (neighbors[v0] - visited):
            dfsIce(v,visited)
        return visited

    # init iceAreas
    iceAreas = [] # list of sets
    for v in ices:
        flatten = set(it.chain(*iceAreas))
        if v not in flatten:
            iceAreas.append(dfsIce(v))
    # print(iceAreas)
    # print()

    # init areaOf
    areaOf = dict()
    for ice in ices:
        for area in iceAreas:
            if ice in area:
                areaOf[ice] = area
                break

    def testIce(path):
        ice = path[-1]
        afterArea = areaOf[ice]-set(path)
        return False if len(afterArea) < len(areaOf[ice]) / 2 else True

    def bfsPaths(startv, goalv):
        pathQueue = [[startv]]
        while pathQueue:
            path = pathQueue.pop(0)
            v0 = path[-1]
            for v in neighbors[v0] - set(path):
                if v == goalv:
                    return path+[v]
                elif field[v]!='X' or testIce(path+[v]):
                    pathQueue.append(path+[v])

    sp = bfsPaths(startv, goalv)
    print(len(sp)-1)

Submission status: Accepted

Solution code:
from collections import deque

while True:
    x, y = map(int, input().split())
    if x == 0:break
    mp = [list("#" * (x + 2))] + [list("#" + input() + "#") for _ in range(y)] + [list("#" * (x + 2))]
    ice_cnt = 0
    ice_dic = []
    vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
    
    
    def ice_search(x, y, ice_cnt):
        for dx, dy in vec:
            if mp[y + dy][x + dx] == "X":
                mp[y + dy][x + dx] = ice_cnt
                ice_dic[ice_cnt] += 1
                ice_search(x + dx, y + dy, ice_cnt)


    for i in range(1, y + 1):
        for j in range(1, x + 1):
            if mp[i][j] == "S":
                sx, sy = j, i
                mp[i][j] = "."
            if mp[i][j] == "G":
                gx, gy = j, i
                mp[i][j] = "."
            if mp[i][j] == "X":
                mp[i][j] = ice_cnt
                ice_dic.append(1)
                ice_search(j, i, ice_cnt)
                ice_cnt += 1

    que = deque()
    que.append((0, sx, sy, [v // 2 for v in ice_dic], 0))
    dic = {}
    dic[(sx, sy, 0)] = 0
    hash_lst = [150 ** i for i in range(len(ice_dic))]
    while que:
        score, px, py, counters, hs = que.popleft()
        if (px, py) == (gx, gy):
            print(score)
            break
        for dx, dy in vec:
            nx, ny = px + dx, py + dy
            if mp[ny][nx] == "#":continue
            elif mp[ny][nx] == ".":
                if (nx, ny, hs) in dic:continue
                dic[(nx, ny, hs)] = True
                que.append((score + 1, nx, ny, counters[:], hs))
            else:
                num = mp[ny][nx]
                if counters[num] <= 0:continue
                new_counters = counters[:]
                new_counters[num] -= 1
                new_hs = hs + hash_lst[num]
                if (nx, ny, new_hs) in dic:continue
                dic[(nx, ny, new_hs)] = True
                que.append((score + 1, nx, ny, new_counters, new_hs))