search

customaddone / beginPython

0 stars 0 forks source link

幅優先探索 #8

Closed customaddone closed 4 years ago

customaddone commented 4 years ago

028ALDS_11_C - 幅優先探索 幅優先探索の基本問題 https://github.com/customaddone/beginPython/blob/361be58f1a3cdf5cdcf7b49c9e3ec2c5177f69f9/cgi-bin/index.py

customaddone commented 4 years ago

029 AtCoder Beginner Contest 007 C - 幅優先探索 mazeの最短経路を求める問題 dpを使って効率的に探索できる https://github.com/customaddone/beginPython/blob/5ce82797c9a575b2176a980bbe6791e67b3d1e4c/cgi-bin/index.py

customaddone commented 4 years ago

030 JOI 2011 予選 5 - チーズ maze最短経路問題 https://github.com/customaddone/beginPython/blob/5600a3962e57a8787f69ae7cfb7c153bbe1ae5b4/cgi-bin/index.py

customaddone commented 4 years ago

033 AtCoder Beginner Contest 088 D - Grid Repainting maze最短経路問題 https://github.com/customaddone/beginPython/blob/3a5349ca3b6a3a668c8fcf1e32d32db0624df7c7/cgi-bin/index.py

customaddone commented 4 years ago

ABC146 D - Coloring Edges on Tree 最小値を求める問題 どうすればK = 1になるか、どうすればK = 2になるか N = 3とかでまず考える →ある頂点を根として子との間の辺について色を決める（例1~2間:4) →子について色1から順にサーチしていく https://github.com/customaddone/beginPython/blob/6dc15b30d0194367336176a139ce4ecf941b19b0/cgi-bin/index.py

customaddone commented 4 years ago

ABC070 D - Transit Tree Path 最短距離を求める問題 点xからyまでの最短距離を求めていきたい→真面目にやるとO(n2)かかるので無理！ 必ず点Kを通るのでKからの最短距離を求めてみる（O(n)) 「前処理を行う」ことが木の最短経路問題では重要 ある点Kからの最短距離についての関数あります https://github.com/customaddone/beginPython/blob/d95151d27784a0e17c2e1636f5d106ceeda3d2c9/cgi-bin/index.py

customaddone commented 4 years ago

ABC168 168 D - .. (Double Dots) 最短経路の求め方＆経路復元 https://github.com/customaddone/beginPython/blob/b8edddd36e237c854d7dd89b2715c32da70b7b3c/cgi-bin/index.py

customaddone commented 4 years ago

ABC039 D - 画像処理高橋君 条件を満たす例を一つ示す→復元前のものを作ってみる https://github.com/customaddone/beginPython/blob/a94555fa5e1aefb930478ec7d10e78ef812a14b2/cgi-bin/index.py

customaddone commented 4 years ago

ABC021 C - 正直者の高橋くん staからの最短距離を求める　→ staからの最短距離でいける通りの数を求める https://github.com/customaddone/beginPython/blob/8d38bd8ef6a42a5fbec36ac3cea7e924f71328ec/cgi-bin/index.py

customaddone commented 4 years ago

C - Alternating Path 黒白黒白... でいける領域の中の#の個数＊・の個数 全ての点について幅優先探索を試みるが、実際かかるのは幅優先探索２、３回 https://github.com/customaddone/beginPython/blob/161da0bde2ec703c0a020e0b12057720cd333a4a/cgi-bin/index.py

customaddone commented 4 years ago

２番目の最短路 https://github.com/customaddone/beginPython/blob/49e11c158cbc63b5f08fd4f8d43ee173a4459f92/cgi-bin/index.py