行列のアルゴリズムのシグナル到達度

Question

アルゴリズムの問​​題が見つかりました。その可能性のある解決策を考えていましたが、「直感的な」ものについて考えることができます。誰かが私に手を貸すことができるかどうかを見てみましょう。

問題は次のとおりです。n*m matrixには、.で表される空白と、%で表される壁があります。 「ルータ」（Rで表される）は、nステップ/セルの範囲のマトリックス内の任意の場所(i,j)に置くことができます。ステップは上/下/左/右のみであることを考慮してください。 ルータの範囲を確認する最も効率的な方法はどれですか？

例（N = 4）

. . . . . . . . . . 
. . % % . . . . . . 
. . % . . . % . . . 
. . . . R . % . . . 
. . % . . . % . . . 
. . % . . . . . . . 

Soltion（#マークが届く信号）

. . . # # # . . . . 
. . % % # # # . . . 
. # % # # # % . . . 
# # # # R # % . . . 
. # % # # # % . . . 
. . % # # # # . . . 

私は私がそれを使用することができると思い、調査及び洪水アルゴリズムを記入発見されました既に再帰的に使用したステップをチェックするための追加のパラメータです。より効率的なアルゴリズムを知っている人はいますか？

ご希望の言語を自由に使用してコードを書くことができます。あらかじめありがとう！

Answer 1

私はBFSを使用することをお勧めします。基本的にはキューを使用してレイヤーごとにノードを訪問します。

t = 0 - Queue = {(0,0)} 
For each element in query, visit north, east, west, south if not 
visited and not wall 
For (0, 0) -> Visit (1, 0), (0, 1), (-1, 0), (0, -1) 
. . . . . . . . . . 
. . % % . . . . . . 
. . % . . . % . . . 
. . . . R . % . . . 
. . % . . . % . . . 
. . % . . . . . . . 

t = 1 Queue = {(1, 0), (0, 1), (-1, 0), (0, -1)} 
For each element in query, visit north, east, west, south if not visited and not wall 
For (1, 0) -> Visit (2, 0), (1, 1), (1, -1) 
For (0, 1) -> Visit (0, 2), (-1, 1) 
For (-1, 0) -> Visit (-1, 0), (-2, 0) 
For (0, -1) -> Visit (-1, -1), (0, -2) 

. . . . . . . . . . 
. . % % . . . . . . 
. . % . # . % . . . 
. . . # R # % . . . 
. . % . # . % . . . 
. . % . . . . . . . 

t = 2 and so on 
. . . . . . . . . . 
. . % % # . . . . . 
. . % # # # % . . . 
. . # # R # % . . . 
. . % # # # % . . . 
. . % . # . . . . . 


t = 3 
. . . . # . . . . . 
. . % % # # . . . . 
. . % # # # % . . . 
. # # # R # % . . . 
. . % # # # % . . . 
. . % # # # . . . .