パナソニックプログラミングコンテスト(ABC195 D - Shipping Center)【Python解答例】
AtCoder Beginner Contest195のD - Shipping CenterについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder
AtCoder Beginner Contest 195 D - Shipping Center
問題文
1 から N の番号がついた N 個の荷物と、1 から M の番号がついた M 個の箱があります。
荷物 i の大きさは Wi で、価値は Vi です。
箱 i には大きさが Xi 以下の荷物を入れることができます。
1 つの箱に 2 つ以上の荷物を入れることはできません。
Q 個のクエリが与えられます。各クエリでは 2 つの整数 L,R が与えられるので、次の問題を解いてください。
問題：M 個の箱のうち、箱 L,L+1,…,R の R−L+1 個の箱が使えなくなってしまいました。 残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。
制約
・1≤N≤50
・1≤M≤50
・1≤Q≤50
・1≤Wi≤10^6
・1≤Vi≤10^6
・1≤Xi≤10^6
・1≤L≤R≤M
・入力は全て整数
解答例
n, m, q = map(int,input().split()) WV = [] for i in range(n): array = list(map(int,input().split())) WV.append(array) WV.sort(key=lambda x:x[1], reverse=True) # 価値Vの降順にソート X = list(map(int,input().split())) Q = [] for i in range(q): array = list(map(int,input().split())) Q.append(array) # クエリ分だけループ for i in range(q): # i番目のクエリ ans = 0 X_copy = X[:] # リストXをコピー del X_copy[Q[i][0]-1:Q[i][1]] # LからRの箱を消去 X_copy.sort() # 箱の大きさを昇順でソート for wv in WV: # 荷物のループ(Vが大きい順) for j in range(len(X_copy)): #箱のループ(大きさが小さい順) if wv[0] <= X_copy[j]: # 探索中の箱に荷物が入れば ans += wv[1] # 価値Viを足して X_copy.pop(j) # 荷物を入れた箱を消去 break print(ans)
解説
それぞれ大きさがWi、価値がViの荷物がN個と、M個の箱があります。
箱iには大きさXi以下の荷物をひとつだけいれることができるという初期条件があります。
Q個のクエリがあり、各クエリでは箱LからRが使えなくなる条件が与えられ、残った箱に入れることができる荷物の価値の最大値をそれぞれ答える問題です。
各クエリごとに箱を消去し、残った箱の小さいものから、できるだけ価値の大きい荷物を貪欲に入れていく方針で進めればOKでした。
上記の方針があるので標準入力はWとVだけVの昇順（大きい順）にソートしました。
あとは各クエリ毎のループをまわします。
リストXは何度も使用するのでクエリ毎にコピーしました。
クエリの条件から使用できない箱をX_copyから消去し、箱の小さい順にソートします。
価値の大きい荷物から、小さい箱の順にループを回していき、入れることができる組み合わせを見つけたら順次荷物を入れていきます。
荷物を入れるたびに価値をansに足していき、入れた箱はリストX_copyから消去しました。
この2重ループを抜けたら価値の合計であるansを出力することを繰り返せばACをとれました。
問題を見ときはDPかと思いましたが、貪欲法で解ける問題でした。
コンテスト中でも解けるように学習を続けていきたいです。
ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
パナソニックプログラミングコンテスト(ABC195 C - Comma)【Python解答例】
AtCoder Beginner Contest195のC - CommaについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder
AtCoder Beginner Contest 195 C - Comma
問題文
高橋君は整数を書くとき、下から 3 桁ごとにコンマで区切って書きます。例えば 1234567 であれば 1,234,567、777 であれば 777 と書きます。
高橋君が 1 以上 N 以下の整数を 1 度ずつ書くとき、コンマは合計で何回書かれますか？
制約
・1≤N≤10^15
・N は整数
解答例
n = int(input()) ans = 0 if n >= 1000: ans += n - 999 if n >= 1000000: ans += n - 999999 if n >= 1000000000: ans += n - 999999999 if n >= 1000000000000: ans += n - 999999999999 if n >= 1000000000000000: ans += n - 999999999999999 print(ans)
解説
問題文の通り1 以上 N 以下の整数を 1 度ずつ書くとき、コンマは合計で何回書かれるか答える問題です。
コンテスト中には解けず、公式解説より良い解法も思いつかないため公式解説と同じ解き方をしています。
Editorial - Panasonic Programming Contest (AtCoder Beginner Contest 195)
公式解説を見たほうが良いと思いますが、一応記事にしていきます…
千の位を表すコンマは999までは出てきませんが1000以上の数字では1つづつあります。
つまりNが1000以上ならN-999個出てきます。
百万の位を表すコンマは99万9999まで出てきませんが100万以上の数字では1つづつあります。
同様にNが100万以上ならN-999999個出てきます。
という感じで、コンマが増える場合ごとにansを足し合わせていけば答えが求まります。
コンテストではごちゃごちゃ演算しましたが、結局微妙に値が違ってACできませんでした。
シンプルで強力な考え方が思いつけるように地道に勉強を続けていきたいです。
ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
パナソニックプログラミングコンテスト(ABC195 A - Health M Death / B - Many Oranges)【Python解答例】
AtCoder Beginner Contest195のA - Health M DeathとB - Many OrangesについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder
AtCoder Beginner Contest 195 A - Health M Death
問題文
魔法使いの高橋君がモンスターと戦っています。
高橋君が魔法を使うと、体力が M の倍数であるモンスターを倒すことができます。体力が M の倍数でないモンスターに対しては何の効果もありません。
高橋君の魔法によって、体力が H のモンスターを倒すことができるでしょうか？
制約
・1≤M≤1000
・1≤H≤1000
・M 及び H は整数
解答例
m, h = map(int,input().split()) if h % m == 0: print("Yes") else: print("No")
AtCoder Beginner Contest195 B - Many Oranges
問題文
みかんがたくさんあります。どのみかんの重さも A グラム以上 B グラム以下であることがわかっています。（みかんの重さは整数とは限りません。）
この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど W キログラムになりました。
選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。
制約
・1≤A≤B≤1000
・1≤W≤1000
・入力は全て整数
解答例
a, b, w = map(int,input().split()) weight = w * 1000 # 単位合わせ flag = True # 組み合わせが起こり得るか判別フラグ # 最大値を求める tmp = weight // a # 余り切り下げ if tmp * a <= weight and tmp * b >= weight: max_num = weight // a else: flag = False # 最小値を求める tmp = -(-weight // b) # 余り切り上げ if tmp * a <= weight and tmp * b >= weight: min_num = -(-weight // b) else: flag = False if flag: print(min_num, max_num) else: print("UNSATISFIABLE")
解説
Aグラム以上、Bグラム以下のみかんをいくつでも選べるとき、重さの合計をWキログラムにできるかどうか、できるならみかんの個数の最小値と最大値を答える問題です。
解説では全探索していましたが、コンテスト中に思いついた方法を記載します。
標準入力のWはキログラム単位でA,Bグラムと単位が違うので単位合わせを行います。
みかんの個数の最大値は重さを余り切り下げでAで割った値が候補(tmp)です。
この値×Aと同じ値×Bの間にW[g]があれば、Wを作り出せることが可能で、最小値となります。
tmp+1個では必ずWを超えてしまうので、候補となる値はtmp以外にないと思います。
みかんの個数の最小値はBで割って余りを切り上げた値(tmp)を候補とします。
最小値と同じようにA×tmpとB×tmpの間にWがあれば、最大値となります。
もし最大値と最小値が存在していたら値を出力し、なければUNSATISFIABLEを出力すればACです。
B問題は余りの切り上げ、切り下げで頭を悩ませましたが解けてよかったです。
全探索で解けることはコンテスト中は全然気が付きませんでした (^_^;)
今回もD問題まで復習していきたいです。
ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
【AtCoder版！蟻本】AOJ0558 Cheese【幅優先探索】
AtCoder版！蟻本の幅優先探索で類題としてあげられているAOJ0558 CheeseをPythonで解いていきます。
リンク
AOJ0558 Cheese
問題文
今年も JOI 町のチーズ工場がチーズの生産を始め，ねずみが巣から顔を出した．JOI 町は東西南北に区画整理されていて，各区画は巣，チーズ工場，障害物，空き地のいずれかである．ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる．
この町には，N 個のチーズ工場があり，どの工場も１種類のチーズだけを生産している．チーズの硬さは工場によって異なっており，硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある．
ねずみの最初の体力は 1 であり，チーズを 1 個食べるごとに体力が 1 増える．ただし，ねずみは自分の体力よりも硬いチーズを食べることはできない．
ねずみは，東西南北に隣り合う区画に 1 分で移動することができるが，障害物の区画には入ることができない．チーズ工場をチーズを食べずに通り過ぎることもできる．すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け．ただし，ねずみがチーズを食べるのにかかる時間は無視できる．
入力
入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≤ H ≤ 1000，1 ≤ W ≤ 1000，1 ≤ N ≤ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'，'X'，'.' からなる W 文字の文字列が書かれており，各々が各区画の状態を表している．北から i 番目，西から j 番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ H, 1 ≤ j ≤ W)，第 i+1 行目の j 番目の文字は，区画 (i,j) が巣である場合は 'S' となり，障害物である場合は 'X' となり，空き地である場合は '.' となり，硬さ 1, 2, ..., 9 のチーズを生産する工場である場合はそれぞれ '1', '2', ..., '9' となる．入力には巣と硬さ 1, 2, ..., N のチーズを生産する工場がそれぞれ 1 つずつある．他のマスは障害物または空き地であることが保証されている．ねずみは全てのチーズを食べられることが保証されている．
解答例
from collections import deque import copy # 入力 h, w, n = map(int,input().split()) maze = [] # 迷路の文字配列 for _ in range(h): maze.append(input()) # 各座標への最短距離の配列（INFで初期化） INF = int(1e9) D = [[INF] * w for _ in range(h)] # 4方向の移動ベクトル dx = [1,0,-1,0] dy = [0,1,0,-1] # スタート位置の探索 for i in range(h): for j in range(w): if maze[i][j] == "S": sy = i sx = j # 硬さxのチーズ位置の探索 def search_cheese(x): for i in range(h): for j in range(w): if maze[i][j] == str(x): gy = i gx = j return gy, gx # 硬さxのチーズ座標を返す # スタートからゴールへの最短距離を求めるbfs def bfs(): que = deque() que.append([sy,sx]) # スタート地点をキューに入れる D_copy[sy][sx] = 0 # スタート地点の距離を0とする # キューが空になるまで探索 while len(que) != 0: p = que.popleft() # 先入れのキューの要素を取り出す if p[0] == gy and p[1] == gx: # ゴールなら探索終了 break for i in range(4): # pから4方向に移動 移動後の点は(nx,ny) ny = p[0] + dy[i] nx = p[1] + dx[i] # 移動可能か、この探索で訪れたことがあるかの判定 if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "X" and D_copy[ny][nx] == INF: # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する que.append([ny,nx]) D_copy[ny][nx] = D_copy[p[0]][p[1]] + 1 # ゴールまでの最短経路を返す return D_copy[gy][gx] # 硬さNまでの最短経路探索 res = 0 # 最短経路 for k in range(n): D_copy = copy.deepcopy(D) tmp = search_cheese(k+1) gy = tmp[0] gx = tmp[1] res += bfs() sy = gy sx = gx print(res)
解説
N個のチーズ工場があり、それぞれ1からNまでの硬さのチーズを生産しています。
スタート地点から硬さNのチーズを食べるまでの最短経路を答える問題です。
この問題も幅優先探索（BFS)で最短経路を求めていきます。
入力を受け取ったあと、BFSの準備として迷路と同じ大きさの配列D（INFで初期化）を用意します。
迷路のスタート地点はSで表されているので、全探索してxy座標をsx,syに代入しました。
硬さiのチーズの位置はプログラムで何度も探す必要があるのでsearch_cheese関数を作成しました。
iを引数として渡すことで硬さiのチーズの位置をgx,gyとして返します。
BFSはスタート地点を渡すことで、gx,gy地点までの最短経路を返す関数です。
最短経路のリストDは以前の探索のデータを引き継いだら間違った答えになりますので、deepcopyしたD_copyに最短経路を記録していきました。
最後に1からNまでのチーズの最短経路をfor文で求めます。
次の目的地であるk+1の硬さのチーズの位置をsearch_sheese関数で求め、BFSで現在地から求めた地点までの最短経路をresに足していきました。
BFSが終わるとゴール地点を次のスタート地点として、次回のループに備えます。
ループを抜ければ求める最短経路がresとなりますので出力すればOKでした。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
AtCoder-ABC194 D - Journey【Python解答例】
AtCoder Beginner Contest194のD - JourneyについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 194 - AtCoder
AtCoder Beginner Contest194 D - Journey
問題文
頂点
1 から頂点 N までの N 頂点からなるグラフの頂点 1 に高橋君がいます。今このグラフに辺は 1 つも張られていません。
高橋君は以下の操作を繰り返します。
操作 :
(今高橋君がいる頂点も含めた) N 個の頂点の中から 1 つランダムに選ぶ。各頂点が選ばれる確率は全て 1/N であり、選択は操作毎に独立である。
今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。
グラフが連結になるまでに行われる操作の回数の期待値を求めてください。
制約
・2≤N≤10^5
解答例
n = int(input()) res = 0 for i in range(1,n): res += n / (n - i) print(res)
解説
N個の頂点があり、すべての頂点にたどり着くまでの操作回数の期待値を答える問題です。
解説であげられている「確率 p(p≠0) で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は 1/p である」という重要な事実を知らず迷走していました (^_^;)
解説の通りに計算するとあっさりACでした…
コンプガチャの期待値とかで検索すると答えに近い大ヒントがごろごろでてきました。
初めてD問題を解くチャンスでしたが逃してしまいましたね (^_^;)
ABC194の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
AtCoder-ABC194 C - Squared Error【Python解答例】
AtCoder Beginner Contest194のC - Squared ErrorについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 194 - AtCoder
AtCoder Beginner Contest194 C - Squared Error
問題文概要
長さ N の数列 A が与えられます。各要素同士の差の 2 乗の和 を求めてください。
制約
・2≤N≤3×10^5
・|Ai|≤200
・入力に含まれる値は全て整数
解答例
n = int(input()) A = list(map(int, input().split())) Sum = [0] * (n + 1) res = (n-1)*pow(A[0],2) Sum[0] = A[0] for i in reversed(range(1,n)): Sum[i] = Sum[i+1] + A[i] res += (n-1)*pow(A[i],2) -(2 * Sum[i] * A[i-1]) print(res)
解説
問題文通り長さ N の数列 A において各要素同士の差の 2 乗の和を答える問題です。
2重ループにできれば簡単ですが、時間が足りないため工夫する必要があります。
自分の解答は数学的に証明できていませんがACはとれた、という感じなのでご注意ください。
N = 3 , j = 1の場合は(A3^2 - A1^2)^2＋(A2^2 - A1^2)^2となり展開すると2A1^2 + A2^2 + A3^2 -2×A1(A2 + A3)となります。
N = 3 , j = 2の場合は(A3^2 - A2^2)^2となり、A2^2 + A3^2 -2×A2×A3です。
答えとなるその和は2(A1^2 + A2^2 + A3^2) - 2{A1(A2 + A3) + A2×A3}になります。
したがって解答は、それぞれのAの要素の2乗に( N - 1 )をかけた値の合計と、Nからj + 1までの要素の合計に-2×Ajをかけた値の和で求まると予想しました。
（Nからj + 1までの要素の合計は配列Sumとしてループにあわせて更新していきました。）
この方針でACできましたが、証明できていないので参考程度の話になります。
結果オーライではありますが、C問題まで解けてよかったです。
コンテスト中に解けなかったD問題も記事にしていきたいます。
ABC194の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
AtCoder-ABC194 A - I Scream / B - Job Assignment【Python解答例】
AtCoder Beginner Contest194のA - I ScreamとB - Job AssignmentについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 194 - AtCoder
AtCoder Beginner Contest194 A - I Scream
問題文
日本において、アイス製品は次の 4 種類に大別されます。
・乳固形分が 15 パーセント以上、乳脂肪分が 8 パーセント以上含まれるものを「アイスクリーム」とする。
・上に当てはまらず、乳固形分が 10 パーセント以上、乳脂肪分が 3 パーセント以上含まれるものを「アイスミルク」とする。
・上のいずれにも当てはまらず、乳固形分が 3 パーセント以上含まれるものを「ラクトアイス」とする。
・上のいずれにも当てはまらないものを「氷菓」とする。
ここで、乳固形分は無脂乳固形分と乳脂肪分の 2 つから成ります。
AtCoder 名物の製品「スヌケアイス」には、無脂乳固形分は A パーセント、乳脂肪分は B パーセント含まれています。
スヌケアイスに上の分類を適用したとすると、4 種類のどれに当てはまるでしょうか ?
答えは「出力」の項に従って整数で出力してください。
制約
・0≤A≤100
・0≤B≤100
・A+B≤100
・A,B は整数
解答例
a, b = map(int,input().split()) if a + b >= 15 and b >= 8: print(1) elif a + b >= 10 and b >= 3: print(2) elif a + b >= 3: print(3) else: print(4)
解説
無脂乳固形分は A パーセント、乳脂肪分は B パーセントのアイスが4種類のどれにあてはまるか答える問題です。
誤読に注意して問題文通りの条件分けを行えばOKです。
自分はラクトアイスの条件「乳固形分が 3 パーセント以上含まれるもの」はA＋Bになる点を勘違いして間違えそうでした (^_^;)
AtCoder Beginner Contest194 B - Job Assignment
問題文
あなたの会社には従業員 1 から従業員 N までの N 人の従業員がいます。
今あなたは仕事 A と仕事 B の 2 つの仕事を受注したので、これらを完了しなければなりません。
従業員 i は仕事 A を Ai 分、仕事 B を Bi 分でこなすことができます。
あなたは仕事 A と仕事 B にそれぞれ従業員を 1 人割り当てます。
同じ従業員を両方の仕事に割り当てても構いませんが、その場合 2 つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となります。
仕事 A と仕事 B に異なる従業員を割り当てた場合、2 つの仕事が終わるのにかかる時間は、各仕事が終わるのにかかる時間の長い方となります。
2 つの仕事が終わるのにかかる時間として考えられる最小の値を求めてください。
制約
・2≤N≤1000
・1≤Ai≤10^5
・1≤Bi≤10^5
・入力に含まれる値は全て整数
解答例
n = int(input()) A = [] B = [] for i in range(n): a, b = map(int, input().split()) A.append(a) B.append(b) res = 1e9 for i in range(n): for j in range(n): if i == j: tmp = A[i] + B[j] else: tmp = max(A[i], B[j]) res = min(res,tmp) print(res)
解説
仕事AとBに割り当てる人を選んで、最短で仕事がおわる時間を答える問題です。
全探索で最短時間を求めました。
もし仕事AとBを同じ人が行う場合はAi＋Biが最短時間の候補です。
仕事Aをiさんが、Bをjさんが行う場合はAiとBjの大きいほうが候補になります。
この候補とresを比較して小さいほうをresとしていき、ループを抜ければ最短時間が求まります。
問題文を正確に理解するのに時間がかかった印象です。
続いてC問題も記事にしていきたいと思います。
ABC194の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
【AtCoder版！蟻本】ABC 007 C - 幅優先探索【幅優先探索 】
AtCoder版！蟻本の幅優先探索で類題としてあげられているABC007 CをPythonで解いていきます。
深さ優先探索と似ている部分もあり、あわせて学習すると理解しやすかったです。
リンク
AtCoder Beginner Contest 007 C - 幅優先探索
問題文
たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。
まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。
今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。
制約
・1 行目には、行数 R(1≦R≦50)と列数 C(1≦C≦50)がそれぞれ空白区切りで与えられる。
・2 行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。スタート地点が sy 行 sx 列にあることを意味する。 1≦sy≦R かつ 1≦sx≦C である。
・3 行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。ゴール地点が gy 行 gx 列にあることを意味する。 1≦gy≦R かつ 1≦gx≦C であり、(gy,gx)≠(sy,sx)であることが保障されている。
・4 行目から R 行、長さ C の文字列が 1 行ずつ与えられる。各文字は . もしくは # のいずれかであり、i 回目 (1≦i≦R) に与えられられる文字列のうち j 文字目 (1≦j≦C) について、その文字が . なら、マス (i,j) が空きマスであり、# なら、マス (i,j) が壁マスであることをあらわす。
・盤面は壁マスで囲まれている。つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス (i,j) について、c(i,j) は #である。また、スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。
解答例
from collections import deque INF = int(1e9) r, c = map(int,input().split()) sy, sx = map(int,input().split()) sy -= 1 sx -= 1 gy, gx = map(int,input().split()) gy -= 1 gx -= 1 maze = [] # 迷路の文字配列 for i in range(r): maze.append(input()) # 各座標への最短距離の配列（INFで初期化） D = [[INF] * c for _ in range(r)] # 4方向の移動ベクトル dx = [1,0,-1,0] dy = [0,1,0,-1] # スタートからゴールへの最短距離を求めるbfs def bfs(): que = deque() que.append([sy,sx]) # スタート地点をキューに入れる D[sy][sx] = 0 # スタート地点の距離を0とする # キューが空になるまで探索 while len(que) != 0: p = que.popleft() # 先入れのキューの要素を取り出す if p[0] == gy and p[1] == gx: # ゴールなら探索終了 break for i in range(4): # pから4方向に移動 移動後の点は(nx,ny) ny = p[0] + dy[i] nx = p[1] + dx[i] # 移動可能か、訪れたことがあるかの判定 if 0 <= nx < c and 0 <= ny < r and maze[ny][nx] != "#" and D[ny][nx] == INF: # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する que.append([ny,nx]) D[ny][nx] = D[p[0]][p[1]] + 1 return D[gy][gx] print(bfs())
解説
R行C列の迷路においてスタート地点からゴール地点への最短距離を求める問題です。
以前に記事にした深さ優先探索の問題と似ています。
ebisuke33.hatenablog.com
深さ優先探索との違いはキューに入れた順番（popleft）で探索している点です。
先入れ先出しで探索し、最短距離のリストDを更新していきます。
ゴールに到着したら探索を終了し、ゴールまでの最短距離を出力すればOKです。
深さ優先探索のあとだったので理解しやすくて助かりました。
迷路探索のような問題に有効なのでしっかり覚えていきたいです。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
