algorithm - 最短経路アルゴリズム - アクセスできないセルを含む行列

Question

インタビューでこんな質問をされました。どうすればいいのかわかりません。基本的に、私はブール値のマトリックスを持っています - 0 はセルにアクセスできないことを表します。開始セルと宛先セルが与えられた場合、アクセスできないセルを飛び越えることなく、開始から宛先までの最短パスを構築するにはどうすればよいですか。4方向すべてに移動できます。

ありがとう

Answer 1

私は単純なフラッドフィルタイプのアルゴリズムを使用します:-

create array of integers equal in size to boolean array => map
set all values in map to 0
set value at (start x, end x) to 1
found path = false
step = 1

while !found path
  for each cell in map where value == step
    for each valid adjacent cell
      if cell == end position
        map [cell] = step
        found path = true
        end search
      end if
      if map [adjacent cell] == 0
        map [adjacent cell] = step + 1
      end if
    end for
  end for
end while

number of steps between start cell and end cell inclusive == step

スタックとキューを使用すると、効率を非常に簡単に向上させることができます。可能なルートのないマップにチェックを入れる必要があります。

Answer 2

この問題を解決するには、単純な幅優先探索で十分です。Python での実装例を次に示します。

入力.txt

4 4
1 1 4 4
1 1 0 0
0 1 0 0
0 1 1 0
0 0 1 1 

解決：

import sys
from collections import deque
sys.stdin = open ("Input.txt", "r")
Table   = []
Queue   = deque()
Visited = set()

n, m = [int (i) for i in sys.stdin.readline().split()]
startx, starty, endx, endy = [int(i)-1 for i in sys.stdin.readline().split()]
for j in xrange(n): Table.append ([int (i) for i in sys.stdin.readline().split()])

if Table[startx][starty] == 0:
    print 0
    sys.exit(0)

def process (X, Y, Dist):
    if (X == endx and Y == endy):
        print Dist + 1
        sys.exit(0)
    if X + 1 != m and Table[X + 1][Y] and (X + 1, Y) not in Visited:
        Queue.append ((X + 1, Y, Dist + 1))
    if Y + 1 != n and Table[X][Y + 1] and (X, Y + 1) not in Visited:
        Queue.append ((X, Y + 1, Dist + 1))
    if X - 1 != -1 and Table[X - 1][Y] and (X - 1, Y) not in Visited:
        Queue.append ((X - 1, Y, Dist + 1))
    if Y - 1 != -1 and Table[X][Y - 1] and (X, Y - 1) not in Visited:
        Queue.append ((X, Y - 1, Dist + 1))

Queue.append ((startx, starty, 0))
while (len(Queue)):
    CurrentX, CurrentY, Distance = Queue.popleft()
    if ((CurrentX, CurrentY) in Visited): continue
    Visited.add ((CurrentX, CurrentY))
    process (CurrentX, CurrentY, Distance)