水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

ABC075 B - Minesweeper をBashで解く

問題

abc075.contest.atcoder.jp

出力するべきは現在見ているマスの周り8マスが # であるものの数である。 現在見ているマス自体が # のときは、そのまま # を出せば良い。

で、ココからが問題で、この問題、Bashで解こうとするとかなりしんどい。

文字列からの取り出し

非常にうまく行かなかったので、2ステップで取り出した。

  1. 行を取り出す
  2. ターゲットとなる文字を取り出す

ここから、ターゲットとなる文字を比較する処理に移った。ドハマリポイントその1。

配列

Bashには配列が存在する。要素外のところにアクセスしてもエラーにはならない。(罠)

ans=() # 初期化、空配列
ans+=${ansline} # 追加
range=(-1 0 1) # 初期化

取り出しは ans[i] のように行える。for-eachみたいなループは for k in ${range[@]}; do

ただ要素外のところにアクセスした際、落ちていないから空白が返るだろうと思ったのだが、メモリ管理の問題からか、 なぜか # が返る時がありバグってWAが出た。マジか。。。。これがドハマリその2。

条件式を書いて弾いたけれども、多分これ、ちゃんと仕様調べないと今後もハマるなあ。。。。

forループの罠

周り8つのマスを調べるため、 seq -1 1 を2重に書いたが、この記載の場合、毎回評価が走ってしまうため、結果としてTLEとなった。

evalするようなコードと同じようなことしているので、当然といえば当然だが、正直短く書くためにこれまで意識していなかった。

当然だが、配列で宣言してそれをfor-eachループで回すほうが早いようだ。 今後、ネストが深いループで固定回数で見られる場合は配列で宣言して用意しておくことを前提にしたい。ドハマリポイントその3。

ソースコード

汚いがこうなった。

abc075.contest.atcoder.jp

#!/bin/bash

read H W
arr=()
for i in `seq ${H}`; do
    read st
    arr+=($st)
done

range=(-1 0 1)
for i in `seq 0 $((H-1))`; do
    ans=''
    tl=${arr[$i]}
    for j in `seq 0 $((W-1))`; do
        t=${tl:j:1}
        if [ ${t} = '#' ]; then 
            ans=${ans}'#'
            continue
        fi

        cnt=0
        for k in ${range[@]}; do
            if [ $((i+k)) -lt 0 ] || [ $((i+k)) -ge ${H} ]; then
                continue
            fi
            al=${arr[$((i+k))]}
            for l in ${range[@]}; do
                if [ $((j+l)) -lt 0 ] || [ $((j+l)) -ge ${W} ]; then
                    continue
                fi
                a=${al:$((j+l)):1}
                if [[ ${a} = '#' ]]; then
                    let cnt++
                fi
            done
        done
        ans=${ans}${cnt}
    done
    echo ${ans} 
done

感想

これまでbashを使いこなせた気持ちでいたので、痛い目を見てもっと勉強しないといけないなと思わされた。

TwitterでたまたまBashでハマっている人がいたので、まさかまさかなあと思っていたけれども、舐めてかかると痛い目を見ますね。精進しましょう…。

追記

はてなブログbashのハイライトに対応していないので、shで指定しなければいけないことを長らくbashを書いていなかったため、忘れていた。