2907 Collecting Beepers

2907 -- Collecting Beepers
というわけでご紹介。今日の練習会でも出た問題でした。
最大で20*20の碁盤目がある。この盤上のいくつかの交点上にポケベルが落ちている（ただしポケベルの数は10以下）。Karelというロボットはある座標から移動を開始し、すべてのポケベルの上を通って回収し、最初の地点まで帰ってくる。ただしロボットはグリッド上しか移動できない。このとき総移動距離がもっとも短くなるときの距離を求めよという問題。
要はノード間の距離がマンハッタン距離となる巡回セールスマン問題の最適解を求めよということ。
GCCで242byte。

k,m,z[99],*x;
f(c,l,h,e){
  for(e=m;e+!h;z[e--]--)
    z[e]++||f(e,l+abs(x[c]-x[e])+abs(x[~c]-x[~e]),h-1);
  h<0&l<k?k=l:0;
}
main(i,b){
  for(gets(x=b);~scanf(k="%d%d%d"+!!i*2,x-i,x+i-1,&m);)
    i=m+i--?i:f(0,0,m)||printf("The shortest path has length %d\n",k);
}

return文がない関数の返値とか使っているどうしようもないソースとなってしまいました。
ノード数が10以下しかないので、全探索で大丈夫。