m*n グリッドが与えられ、各セルは「b」または「w」のいずれかでマークされます。黒と白の絵の具も与えられます。それぞれ任意の色 (黒または白) の k ストロークを使用できます。ストロークは、同じ行の連続する無色のセルの色付けとして定義されます (つまり、ストロークは行の長さを超えることはできません。そのストロークの終わりである行の終わりの前にブラシを拾います）。目的は、エラーの数を最小限に抑えることです。セルを間違った色でペイントするか、セルがペイントされていない場合にエラーが発生します。最適な戦略は何ですか？
質問する
129 次
1 に答える
0
1 行の問題 (特定の BW 行で k ストロークの最小エラー数) の既知の解決策を使用して、問題を解決できます。
行ごとに、指定されたストローク数のエラー数のリストを作成しますk_i = [0, 1, ..., min k needed to cover i-th row]。これでn、(異なるサイズの) リストができました。kどの行で「k」ストロークを使用するかを見つけるには、リストの先頭から、どのストロークがほとんどのセルをカバーするかを繰り返しポップするだけで十分です。
したがって、主なタスクは1行の問題を解決することであり、方法がわかりません:-)
C を連続した色の変化の数とします。行をカバーするための最小ストローク数よりもceil( (C+1)/2 ). これは、行全体をカバーする最初のストロークと最後のストロークの最も離れた変更の間の次のストロークでストロークの色を交互にすることで実行できます。最初のストロークには、一方 (または両方) の端の色があります。
行全体をカバーするのに十分なストロークがない場合、同様のアプローチでエラーの数を見つけることができると思います。1 つの色の一部の範囲を省略する必要があります。それは次の方法で行われます。
境界上にない色から始めて (最初のストロークを省略)、
一部のストロークは、最後のストロークの最も遠い変化の間ではなく、より近い変化の間にあります。
よくわかりませんが、最小の同じ色のパーツをいくつか見つけるだけで十分なようで、それがエラーとして残ります。おそらく、これらのパーツが端からどれだけ離れているかが重要です。
それは今のところ...
于 2012-09-06T17:12:13.463 に答える