結果

問題 No.340 雪の足跡
ユーザー LeonardoneLeonardone
提出日時 2016-01-30 07:21:58
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 2,609 bytes
コンパイル時間 55 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 37,024 KB
最終ジャッジ日時 2024-09-21 19:02:58
合計ジャッジ時間 7,051 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
13,756 KB
testcase_01 AC 11 ms
6,940 KB
testcase_02 AC 11 ms
6,944 KB
testcase_03 AC 11 ms
6,940 KB
testcase_04 AC 12 ms
6,944 KB
testcase_05 AC 12 ms
6,944 KB
testcase_06 AC 12 ms
6,940 KB
testcase_07 AC 11 ms
6,940 KB
testcase_08 AC 12 ms
6,940 KB
testcase_09 AC 11 ms
6,944 KB
testcase_10 AC 11 ms
6,940 KB
testcase_11 AC 28 ms
6,944 KB
testcase_12 AC 21 ms
6,944 KB
testcase_13 AC 29 ms
6,940 KB
testcase_14 AC 416 ms
8,192 KB
testcase_15 AC 529 ms
8,192 KB
testcase_16 AC 310 ms
7,296 KB
testcase_17 AC 741 ms
8,576 KB
testcase_18 AC 588 ms
8,576 KB
testcase_19 AC 750 ms
8,320 KB
testcase_20 TLE -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます

ソースコード

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
    
    k = True
    while k:
        k = False
        for y in xrange(h):
            for x in xrange(w):
                if not f[y][x]:
                    continue
                c = 0
                if hr[y][x]:
                    c += 1
                if vr[y][x]:
                    c += 1
                if x > 0 and hr[y][x-1]:
                    c += 1
                if y > 0 and vr[y-1][x]:
                    c += 1
                if c < 2:
                    f[y][x] = False
                    k = True
    
    g = ((h - 1) << 10) | (w - 1)
    cu = [0]
    f[0][0] = False
    f[h-1][w-1] = True
    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