幅優先探索

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 参考記事をPythonで実装した。 注意点としてBFSのcontinueする条件は s[nx][ny]!='.' とすると s[nx][ny]='G'(ゴール) のときをスルーしてしまうので一生ゴールにつかなくなる。 from collections import deque h,w=map(int,input().split()) s=[input() for _ in range(h)] #スタート、ゴ…

atcoder.jp・参考： www.youtube.com・考え方：bfsで解く。1から行ける頂点の距離をdist1、N1+N2から行ける頂点の距離をdist2とする。あとはそれぞれのmaxを取って+1したのが最大の距離になる。 from collections import deque #入力 n1,n2,m=map(int, input().split()) n=n1+n2 g=[[]for _ in range(n)] for _ in range(m): a,b=map(int, input().split()) a-=1 b-=1 g[a].append(b) g[b].appen…

・問題： atcoder.jp・参考： Submission #16162979 - AtCoder Regular Contest 005 AtCoder ARC 005 C - 器物損壊！高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録・0-1BFS： 01-BFSのちょっと丁寧な解説 - ARMERIA・ダイクストラ法： グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube・0-1BFSを使う。壁の有無で0，1を重さとしてBFSするものをいう。ダイクストラ法の重さが0，1になったもので、0のときはdequeの左から入れて1のときは右から入れる。こうすると0の…

・問題 atcoder.jp ・参考 AtCoder AGC 033 A - Darker and Darker (緑色, 300 点) - けんちょんの競プロ精進記録 ・考えたこと：DFSかBFSを使うことは分かったが具体的なやり方は思いつかなかった。上の記事を参考にして、スタートを'#'としてbfsをする。'#'からの距離distが最大のものが答えとすれば良いということが分かった。・注意点：pypyで提出してください。 ・実装例： from collections import deque H,W=map(int,input().split()) field=[] for _ in ran…

atcoder.jp・注意点：TLEする可能性があるのでPypyで提出してください。・説明：幅優先探索を使ってとく。プログラムの流れはgoalにチーズの位置を入れて、チーズの位置をゴール(gx,gy)、次のループでゴールをスタートにして(sx=gx,sy=gy)幅優先探索をする。また幅優先探索では、for文のはじめで前のループの結果を引き継がないように初期化する必要がある。・実装： from collections import deque H,W,N=map(int,input().split()) field=[] for _ in range(H): field.append(list(…

・問題 atcoder.jp・参考： スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita・注意点：参考文献を見れば基本大丈夫だが、スタートとゴールの座標をマイナス1する必要がある。(sx-=1,,,のように)・実装： from collections import deque H,W=map(int,input().split()) sx,sy=map(int,input().split()) gx,gy=map(int,input().split()) #1つ下げる sx-=1 sy-=1 gx-=1 gy-=1 field=[] for _ in range(H): …

・参考： BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita・内容：上の記事を参考にpythonでBFSを書いた。queueはcollectionsのdequeのほうが早いらしい。dequeはque=deque() #que.append(i)でappend,que.popleft()で左を取り出してキューから左の要素が消える。 queueはque=queue.Queue() #que.put(i),que.get()で同じことができる。・実装：頂点0からの距離distを求めるもの。 from collections import deque import q…