問題 グリッド上に連結した池がある。これをぐるっと回って戻ってくるための最短経路を求めよ。ただし8連結方向に移動できる。 やりかた 通ったけど多分嘘解法。凸包。まず池の周りを4連結で囲むように印をつける。その印にたいして凸包を計算して池を一周す…

問題 やりかた 木の直径を求める問題。グラフ上の適当な点からはじめて最も遠い点を見つける。続いてその点から最も遠い点を探すとその間が直径になる。 メモリ量、制限時間ともにシビア。グラフは隣接リストで持たずに、ある頂点に対する４方向の連結情報を…

問題 グリッド上の格子点を直径1.6mの円形のロボットがスタート地点からゴール地点まで移動する。グリッドの一部に障害物があり、ロボットを障害物にぶつけてはいけない。ロボットは一回の移動で左右に向きを変えるか、1~3つ分の格子点を直進することができ…