私は今日インタビューを受けて、この質問をしました！MSのペイントコードはインタビューで尋ねました
コードMSペイントプログラム。 N * Nピクセルの面積。与えられたピクセルと色は、ピクセルの色を目的の色に変更し、隣接するピクセルの色が同じである場合は変更します。
私は、n個の* n個の配列を取るでしょうし、所与の画素をチェックして、隣接に移動しますと言って、それに近づきました。 （x + 1、y + 1）、（x + 1、y）、（x、y + 1）を探す。 ）、（X-1、Y）、（X-1、Y-1）...
が、インタビュアーが幸せではありませんでした誰かが私より優れたアルゴリズムを用いて別の方法を提案することができます。..より良い空間を有していると時間の複雑さ！
面接官はおそらく、フラッドフィルを要求していました。これは簡単なアプローチではできません。
これがflood-fillの場合、対角線は隣接としてカウントされません。
最も単純なフラッド・フィルは、アレイ上の各隣接画素上で再帰呼び出しです。大規模なグリッド上で単純な方法を使用すると、スタックが不足する可能性が非常に高くなります。
右の方法は、開始位置をエンキューし、デキューし、ピクセルの色が元の色であるかどうかを確認し、左と右の塗りつぶしをスキャンし、上と下のすべてのピクセルをエンキューします。キューが空になるまで続けます。あなたが話している
アルゴリズムは塗りつぶしと呼ばれています。よく知られたアプローチについては、Wikipedia.
DFSアルゴリズムを使用してこの問題を解決できます。与えられたピクセル（xi、yi）は、ピクセルノード（xi-1、yi-1）、（xi-1、yi）、（xi、yi + 1） （xi、yi）に隣接する画素ノードとしての（xi + 1、yi-1）、（xi + 1、yi + 1）、（xi-1、yi + 。 ノード（xi、yi）から始まるDFSを実行して、パス内の各ノードに色付けし、別の色ノードをヒットしたらバックトラックします。 DFSはO（V + E）の時間複雑性が良い。