結果

問題 No.340 雪の足跡
コンテスト
ユーザー Leonardone
提出日時 2016-01-30 07:09:26
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 2,055 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 35,456 KB
最終ジャッジ日時 2024-09-21 19:02:25
合計ジャッジ時間 6,722 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 15 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
# yukicoder My Practice
# author: Leonardone @ NEETSDKASU
# ------------------------------------------------------
def gs():   return raw_input().strip()
def gi():   return int(gs())
def gss():  return gs().split()
def gis():  return map(int, gss())
def nmapf(n, f): return [f() for _ in range(n)]
def ngs(n): return nmapf(n, gs)
def ngi(n): return nmapf(n, gi)
def ngss(n): return nmapf(n, gss)
def ngis(n): return nmapf(n, gis)
def arr2d(h,w,v=0): return [[v] * w for _ in range(h)]
def divMod(v,d): w = v // d; return w, v - w * d
# ------------------------------------------------------


def solve():
    w, h, n = gis()
    hr = arr2d(h,w,False)
    vr = arr2d(h,w,False)
    f = arr2d(h,w,True)
    
    for _ in xrange(n):
        m = gi()
        b = gis()
        for i in xrange(m):
            b1 = max(b[i],b[i+1])
            b2 = min(b[i],b[i+1])
            b1y, b1x = divMod(b1,w)
            b2y, b2x = divMod(b2,w)
            if b1y == b2y:
                for x in xrange(b2x,b1x):
                    hr[b1y][x] = True
            elif b1x == b2x:
                for y in xrange(b2y,b1y):
                    vr[y][b1x] = True
    
    g = ((h - 1) << 10) | (w - 1)
    cu = [0]
    f[0][0] = False
    for i in xrange(h * w):
        nx = []
        for v in cu:
            if v == g:
                print i
                return
            y = v >> 10
            x = v & 1023
            if x > 0 and f[y][x-1] and hr[y][x-1]:
                f[y][x-1] = False
                nx.append((y << 10) | (x - 1))
            if x < w - 1 and f[y][x+1] and hr[y][x]:
                f[y][x+1] = False
                nx.append((y << 10) | (x + 1))
            if y > 0 and f[y-1][x] and vr[y-1][x]:
                f[y-1][x] = False
                nx.append(((y - 1) << 10) | x)
            if y < h - 1 and f[y+1][x] and vr[y][x]:
                f[y+1][x] = False
                nx.append(((y + 1) << 10) | x)
        cu = nx
        if len(cu) == 0:
            break
    print 'Odekakedekinai..'
    
solve()
0