semiexp https://blog.hatena.ne.jp/semiexp/ Algorithmer’s note https://semiexp.hatenadiary.org/ Algorithm TopCoder 問題 グリッド状の土地があり、金鉱、銀鉱、ワークスペースがある。それ以外のマスには芝生か岩である。 何人かの労働者を雇って、金銀の採掘をさせたい。各労働者には1つずつの金鉱、銀鉱、ワークスペースが与えられる。これらは複数人の労働者で共有してはいけない。 ワークスペースから、金鉱、銀鉱までの距離は、それぞれK以下でないといけない。移動の際に通れるマスは芝生のマスのみである。 雇える労働者の最大数を求めよ。 解答 ワークスペースと、金鉱、銀鉱の間で、つなげるかどうかの表をまず作成する。 これは、BFSによって各ワークスペースからの距離を求めることでできる。 その後、[起点]->[金鉱]->[ワーク… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsemiexp.hatenadiary.org%2Fentry%2F20110925%2F1316942060" title="TopCoder SRM422 Div1Hard - Algorithmer’s note" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-09-25 18:14:20 rich https://semiexp.hatenadiary.org/entry/20110925/1316942060 1.0 100%