N x Mの行列では、最適時間に隣り合っている数に等しい隣人の最大数を見つける

Question

これは私の宿題ではありません。それは私がオンラインで見つけ出したものです。その周りに頭を下げる。

N×Mの行列には1と0だけが与えられます。 。隣人は、上下左右に番号を付けることができます。大部分の数字は8つの隣り合いを持ち、一方の数字は5つあり、4つの角のそれぞれに3つあります。マトリックスの数字に等しい隣人の最大数を見つける必要があります。

問題は、行列（N×Mチェック）のすべての数値をチェックせずにそれを行う方法がわかりません。

Answer 1

マトリックスのすべての要素を確認することはできません。 「チェッカーボード」マトリクスの

思う：

1 0 1 0 1 0 1 0 
0 1 0 1 0 1 0 1 
1 0 1 0 1 0 1 0 
0 1 0 1 0 1 0 1 
1 0 1 0 1 0 1 0 
0 1 0 1 0 1 0 1 
1 0 1 0 1 0 1 0 
0 1 0 1 0 1 0 1 

当面のエッジを無視するには、すべての要素は、4つの等しいネイバーを有しています。しかし、いずれかの要素を否定すると（0から1または1から0に変わります）、いくつかの位置には5つの等しい近隣があります。したがって、チェッカーボード行列を処理するときに、行rと列cの要素を決して見ないアルゴリズムを考え出すと、上記のチェッカーボード行列とチェッカーボードの2つの可能な行列の1つに対して間違った答えが得られます。位置（r、c）が否定されています。