問題26 : 最短経路探索

内容

シンプルな最短経路探索問題です。

シェル芸

cat input.txt | sed -E 's/(.)/\1 /g' | awk '{for(i=1;i<=NF;i++){a[NR,i]=$i}}END{for(i=1;i<=5;i++){for(j=1;j<=5;j++){b[i,j]=999}};b[1,1]=0;c=0;while(c==0){for(i=1;i<=5;i++){for(j=1;j<=5;j++){if(a[i,j]!="#"){if(i>1&&a[i-1,j]!="#"&&b[i-1,j]+1<b[i,j]){b[i,j]=b[i-1,j]+1};if(j>1&&a[i,j-1]!="#"&&b[i,j-1]+1<b[i,j]){b[i,j]=b[i,j-1]+1}}}};if(b[5,5]!=999){c=1;print b[5,5]} }}'

解説

awkの疑似的な二次元配列でゴリ押ししましょう。最短経路の求め方はいろいろありますが、今回は、隣のマスを見て距離を更新していくようにしています。

ウェブサイト

シェル芸オンラインジャッジ : https://shellgei-online-judge.com/

LEAVE A COMMENT