空のノート - note of void.


Menu

Navi
Auther
Webclap
Search
Categories
Archives
Recent
Comments
Trackbacks
Advertise
RSS1.0 XML


Entries


2006-01-17

だんごチェック

唐突ですが、私SRCの方ではUnnamedと名乗らせて頂いています。折角機能があるので、あまり関係ないサイトですがトラックバックを試しつつ反応でも。…ちなみにドット絵の方はまだまだです。まことに申し訳ない。一応忘れてません。

で本題ですが、先日ハク様のBlogアルゴリズム大会と称す面白そうな突発イベントがあったのに気づきまして。時期を外してしまいましたけれども、私もちょっと組んでみました。

# ところで、こういうイベントを継続的に行って、この間の汎用ライブラリとかの取っ掛かりにでもなれば、それもまた面白いですね。

# max_cluster() -> 最大の塊ユニット数
# arg : なし
max_cluster:
    local x y i
    foreach "味方" "出撃"
        incr i
        x = X()
        y = Y()
        _x[i] = x
        _y[i] = y
        _ps[x, y] = i
    next
    local psc = Count(_ps)
    local s
    local c = 0
    local max = 0
    foreach s in _ps
        c = _cluster(_ps[s])
        incr psc (- c)
        if max < c then
            max = c
        endif
        if psc <= 0 then
            break
        endif
    next
    unset _x
    unset _y
    unset _ps
return max

_cluster:
    local id = Args(1)
    if not id then
        return 0
    endif
    local x = _x[id]
    local y = _y[id]
    unset _ps[x, y]
return (1 + _
    _cluster(_ps[x + 1, y]) + _
    _cluster(_ps[x - 1, y]) + _
    _cluster(_ps[x, y + 1]) + _
    _cluster(_ps[x, y - 1]) )

ほとんどLuciedさんのだんごチェック1と同じですね……一応、一から考えてはみたのですが。

やはりset変数と再帰呼び出しを使っています。SRCでは配列の受け渡しが出来ないし名前空間もないので、ある程度はどうしようもないところもありますね。再帰展開は面倒…じゃない、保守しにくくなりますし。肝心の性能の方は、塊が大きいほど他と比べて速くなると思います(が、塊があまりに大きいとSRCの再帰深度制限に引っかかる可能性もあります。大体40マスくらいまで。AWARのあのシーンは駄目かも)。

ところで、他の方の案だと、ユニットが分散しているときに必ずしも最も大きな塊のユニット数を返さないように思うのですが、これは仕様なのでしょうかね。「全員くっついているとき」という条件もついていますし、途中でループを打ち切っても良いのですが、やはり数がわかる方が便利でしょう。

TrackBack ping me at:

http://abyss.dw.land.to:8080/blosxom/src/src000.trackback

WriteBacks

[SRC]だんごチェック再び

もう触れることは無いと思っていた「だんごチェック」ですが、[http://d.hatena.ne.jp/tonkati/20060115#1137361063:title=tonkatiさん]と[http://abyss.dw.land.to/blosxom/src/src000.html:title=Unnamedさん]からツッコミを頂いたので、釈明という名の言い訳を。(どっちも一緒 とりあえず、だんごチェックの開発コンセプトは、Unnamedさんがおっしゃっているように ”全ての味方が誰かとくっつい ...

trackback: Eclipse - 2006/1/17 23:27:16

Leave a comment...

usable: <em> <strong> <q> <sub> <sup> <code> <cite>

投稿された内容は管理者によって予告無く削除される場合があります。

Name:
URL/Email: (optional)
Title: (optional)
Comments: