Gamers (UVa Live Archive Europe - Southeastern - 2010/2011 Bucharest (Romania))Comments

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4821

問題

R*Cの各グリッド上にゲームセンターがある。各ゲームセンターは一つのゲームを提供し、そこをホームにしているゲーマーがいる。各ゲーマーは全ての種類のゲームをプレイしたいのだが、自分のホームではプレイしない。また、ゲーマーは、一回ゲームをプレイする度に自分のホームへ戻る。各ゲーマーが最小の移動距離で全ての種類のゲームをプレイした場合の移動距離の総和を求めよ。
1<=R,C<=1000
1<=ゲームの種類<=10

解法

ゲームの種類ごとにbfsを行い最も近くのゲームセンターまでの距離を計算する。bfsは移動方向が右下、右上、左上、左下という風に制限された状態で合計4回行うとその種類のゲームをするための(自分のホームを除いた)最小距離が全て計算できる。メモリ制限、TLEがきついので色々工夫すること。