結果

問題 No.971 いたずらっ子
コンテスト
ユーザー 👑 Kazun
提出日時 2022-01-03 02:33:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,559 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 287,344 KB
最終ジャッジ日時 2024-10-12 08:43:14
合計ジャッジ時間 7,636 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Dijkstra_Heap:
    inf=float("inf")

    def __init__(self,N):
        """ ダイクストラ専用のヒープを生成する.
        """

        self.N=N
        self.remain=N

        self.value=[Dijkstra_Heap.inf]*N
        self.dist=[-1]*N
        self.tree=list(range(N))
        self.inverse=list(range(N))

    def __bool__(self):
        return self.value[0]<Dijkstra_Heap.inf

    def __swap(self, i, j):
        """ ヒープ木の第 i 要素と第 j 要素を交換する. """

        self.value[i],self.value[j]=self.value[j],self.value[i]

        p=self.tree[i]; q=self.tree[j]

        self.tree[i],self.tree[j]=q,p
        self.inverse[p],self.inverse[q]=j,i

    def pop(self):
        assert bool(self.remain)

        p=self.tree[0]
        d=self.value[0]

        self.dist[p]=d
        self.remain-=1

        self.__swap(0,self.remain)
        self.value[self.remain]=Dijkstra_Heap.inf

        V=self.value
        k=0
        while True:
            if 2*k+1>=self.N:
                break

            if 2*k+2==self.N:
                if V[k]<=V[2*k+1]:
                    break
                j=2*k+1
            else:
                u=V[2*k+1]; v=V[2*k+2]

                if V[k]<=u and V[k]<=v:
                    break

                if u<=v:
                    j=2*k+1
                else:
                    j=2*k+2
            self.__swap(k,j)
            k=j

        return (p,d)

    def __setitem__(self, index, value):
        if self.dist[index]!=-1:
            return

        V=self.value
        i=self.inverse[index]

        if V[i]<=value:
            return

        V[i]=value
        while i>0 and V[(i-1)>>1]>V[i]:
            j=(i-1)>>1
            self.__swap(i,j)
            i=j

    def __getitem__(self, index):
        return self.dist[index] if self.dist[index]>=0 else self.value[self.inverse[index]]

    def final_answer(self, index,default):
        return self.dist[index] if self.dist[index]>=0 else default

#==================================================
H,W=map(int,input().split())

A=[]
for _ in range(H):
    A.append(list(map(lambda x:1 if x=="k" else 0,input()))+[-1])
A.append([-1]*(W+1))

Q=Dijkstra_Heap(H*W); Q[0]=0

while Q:
    x,t=Q.pop()
    i,j=divmod(x,W)

    if x==H*W-1:
        break

    if i!=H-1:
        if A[i+1][j]==0:
            Q[(i+1)*W+j]=t+1
        else:
            Q[(i+1)*W+j]=t+1+((i+1)+j)

    if j!=W-1:
        if A[i][j+1]==0:
            Q[i*W+(j+1)]=t+1
        else:
            Q[i*W+(j+1)]=t+1+(i+(j+1))

print(Q[H*W-1])
0