総数を求めるアルゴリズム

Question

下の表のように方向を決める数字があり、その方向に＋１をしたいです。
〇の部分が3の場合、〇の下のマスに＋１をするといった感じです。
また＋１されたマスが3の場合、下のマスに＋２をして最終的な累積量を知りたいです。
|0|x1|x2|x3|:|x1|x2|x3|
|:--|:--:|--:|
|y1|6|7|8|:|↖|↑|↗
|y2|5|〇|1|:|←|〇|→
|y3|4|3|2|:|↙|↓|↘

例えば下の表であれば、求めている実行結果は一番右の表の部分です。
|0|x1|x2|x3|　:|x1|x2|x3|:|x1|x2|x3
|:--|:--:|--|
|y1|3|1|8|:|↓|→|↗|:|0|1|8|
|y2|2|7|7|:|↘|↑|↑|:|1|0|5|
|y3|1|8|7|:|→|↗|↑|:|0|3|0|

Q = np.full((3,3),0)

for a in range(3):
    for b in range(3): 
            if K[a][b] == 1:
                Q[a][b+1] += 1
            elif K[a][b] == 2:
                Q[a+1][b+1] += 1
            elif K[a][b] == 3:
                Q[a+1][b] += 1
            elif K[a][b] == 4:
                Q[a+1][b-1] += 1
            elif K[a][b] == 5:
                Q[a][b-1] += 1
            elif K[a][b] == 6:
                Q[a-1][b-1] += 1
            elif K[a][b] == 7:
                Q[a-1][b] += 1
            elif K[a][b] == 8:
                Q[a-1][b+1] += 1

print(Q)

それぞれの方向で場合分けして最初の＋１をするところまでは、何とか出来たのですが累積量まで自力でたどり着けませんでした。
自分の実行結果↓
|0|x1|x2|x3|
|:--|:--:|--:|
|y1|0|1|2
|y2|1|0|2|
|y3|0|2|0|

Comments

[jun68ykt]

ご質問にある、
> 例えば下の表であれば、
の事例で、初期状態の行列のy2行x2列が、はじめ 7 だったのが、矢印を要素とする行列による演算によって、0 になっていますが、これはどのような計算を経て7 から 0 になったのか、算出手順を追記いただければと思います。

[meg_]

コード中のKとACCは何ですか？

[yonhark0]

meg_さん
すみません、ACCはＱの間違いです。
Ｋは、「例えば下の表であれば」の1番左の表です。

[yonhark0]

jun68yktさん
初期状態の左の行列は矢印を数字で表していて、右の行列のx2y2は矢印が入ってきていないため0になっています。
わかりづらくてすみません。

Answer 1

直接の回答ではないですが、グラフ(特に有向非巡回グラフ=DAG)としてみれば、「各ノードに到達可能なノードの個数(自分除く)」が欲しい答えになります。こちらの方法の方がより簡単に解けるかもしれません。

もしDAGになっていない(つまりサイクルがある)とき答えがどうなるかは質問文から明らかではないので考慮していません。

Comments

[yonhark0]

そんな方法があるんですね、試してみます。
ありがとうございます！