5

これはインタビューの質問です：

行列の場合、1 つのエントリに 1 を追加すると、周囲のすべてのエントリ (上、下、左、右) にも 1 が追加されるという操作を定義します。正の行列が与えられた場合、その行列がは、そのような操作を使用してゼロ行列から構築されます。

問題を解決するための効率的なアルゴリズムは何ですか?

現在考えられるのは、バックトラッキングを使用して可能なすべての組み合わせを試すことですが、これは明らかに効率的ではありません。質問は消灯ゲームのようなものですが、ここでは 0/1 ではないため、より複雑になります。

ありがとう。

編集：

例えば：

3 3 can be constructed from 0 0 -> 1 1 -> 2 2 -> 3 3
1 2                         0 0    1 0    1 1    1 2
4

2 に答える 2

1

線形代数？

Cell i,j is touched x<sub>ij</sub> times.

n 2変数と方程式。解決する。O(n^6)ガウス法では、他のより高速な方法が存在する可能性があります。

また、マトリックスは特殊なので高速化できるかもしれません。

于 2012-09-11T02:57:34.887 に答える
0

私はいくつかのものを見つけました（2x2マトリックスの場合）、最初にそれらを共有したいと思います-
マトリックス内のすべての要素の合計は3で割り切れる必要があります（それからのみ可能です）。
-与えられた行列を、許可された操作ステップの形式で表現する必要があります

3 3  -> 2* 1 1    +    1* 1 1
1 2        0 1            1 0

これができない場合もあります。

5 3  ->2* 1 0  +   2* 1 1     = 4 2
2 4       1 1         0 1       2 4

5 3   -   4 2     = 1 1 (this is not allowed operation)
2 4       2 4       0 0
于 2012-09-11T06:22:53.073 に答える