結果

問題 No.340 雪の足跡
ユーザー Leonardone
提出日時 2016-01-30 07:01:08
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 2,044 bytes
コンパイル時間 43 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 35,584 KB
最終ジャッジ日時 2024-09-21 19:02:18
合計ジャッジ時間 6,481 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 WA * 1
other AC * 13 WA * 2 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+1):
                    hr[b1y][x] = True
            elif b1x == b2x:
                for y in xrange(b2y,b1y+1):
                    vr[y][b1x] = True
    
    cu = [0]
    f[0][0] = False
    for i in xrange(h * w):
        nx = []
        for v in cu:
            y = v >> 10
            x = v & 1023
            if x == w - 1 and y == h - 1:
                print i
                return
            if x > 1 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 > 1 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