探索2178号迷宮

質問元:https://www.acmicpc.net/problem/2178
解くのに1時間もかかったような….(これも長足の進歩です)
2ヶ月前までは、アルゴリズム自体についても、空前絶後の文字列だったのだろうか.私は関連する問題だけを解決して、簡単な実現問題だけを試してみましたが、私は今でも手を伸ばして自分に教えて、博士の助けがなければ、自分でアルゴリズムを書くことができます(もちろんこれは基礎的な問題です...)

思考過程.

BFSを使うことにしました.(原因は以下の通り)
1.私のBOARDでの位置によって、東西南北、すべての方向を探求する
->最初はINDEXを直接変数に減らしていましたが、コード行が重複しているのでdicという方向変数をfor文として扱います.
2.通ったところでVISITED処理をします(ここで待って!いったい通った道が最短距離になるのでしょうか?結果は無理です.)
->したがって、通過する位置は移動できない0と見なされ、0に変更されます.
3.目的地に着いたらifドアで閉じる...いいですか.
->BFSなので、height(移動距離)単位でグラフィックをナビゲートし、最終的に最短距離に移動し、目的地に着いたときに最も速く到着します.
第3段階でミスがあった.位置(pos)を変更するたびに、最初にcountが行われます.この場合

結果は、1−>3−>Fが3、1−>2−>3−>Fが4であるべきである.
そこで,ツリーにおけるHEIGHTの概念に基づいて,ここで移動する距離に適用する.これを実現するために、tmp(このheightのノード数)、next tmp(nextheightのノード数)、heightなどの変数が導入され、1つのheightのノードをクエリーするたびにnext tmpに値が追加され、queでtmpがポップアップされると、そのheightのすべてのノードがクエリーされます.tmp=next tmp,height+1,次のheightに進みます.
いくつかの最短経路、特殊経路を求める場合、BFSはDFSよりも有利である.理由を推測してみましょうか.このパスではなくDFSを使用して実装する場合は、問題が発生するまで他のパスを再参照する必要があります.これにより、通常時間の複雑さが増大します.

import sys
from collections import deque

N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))

board = [[0 for f in range(M+2)]]+[[0]+list(map(int,sys.stdin.readline().rstrip("\n")))+[0] for m in range(N)]+[[0 for l in range(M+2)]]
h,w = 1,1
pos = deque([[h,w]])
board[pos[0][0]][pos[0][1]]=0
dic = [[0,1],[1,0],[0,-1],[-1,0]]
height, tmp, next_tmp = 0, 1, 0

while pos :
    #동,남,서,북
    now=pos.popleft()
    tmp-=1
    if (now[0]==N) and (now[1]==M) :
        print(height+1)
        break
    #코드 동일 recycle
    #결국 몇번째 height냐 => 정답
    for i in range(4) : # 0,1,2,3
        if board[now[0]+dic[i][0]][now[1]+dic[i][1]] == 1 :
            pos.append([now[0]+dic[i][0],now[1]+dic[i][1]])
            board[now[0]+dic[i][0]][now[1]+dic[i][1]]=0
            next_tmp+=1
    if tmp==0 :
        tmp = next_tmp
        next_tmp = 0
        height+=1

結果は正しいですが、実行時間は他の人より平均的に長いので、問題をどのように解決すれば効率的になるかを学びましょう.
! 一人で勉強するために参考書を書きましたが、問題があれば削除します.

dllwonans 0001の答え:次のレベル(移動距離)に移動することを考慮するために、クエリーのすべてのノードに変数を直接適用するカウントを行いました.ノードをクエリーおよび移動できる場合はdequeに追加されるため、ノードの数はdequeに追加されます.このセットの概念を使用して、クエリーのすべてのノードを説明します.setは、任意の位置から到達可能な次の位置(A)をすべて格納する.一周した後、setは再びAから着くことができるすべての位置(B)を保存します.我々はDequeに縛られない能力を育成し,実現したい機能に応じて適切な関数,資料構造などを考えるべきである.

Dequeを使用する他の方法
1)Boardと同じサイズでcountリストを作成して移動する場合は、前の移動パス+1を使用します.(先の値から以下の値、DPを決定)
2)1つのheightのすべてのNODEを共通に照会した後にheight+1を行うことができる.この場合、クエリ方式に差があります.また、while文には、ノードにリンクされたすべてのノードを参照するためのfor文が作成され、while文が終了する前にすべてのノードをクエリーしてheight+1することができるノードを参照するための変数も作成されました.