Efficient algorithm to search for a target in a matrix given only the path it took?

Question

The problem is as follows: we have an N by N matrix, A. A bird starts at (0, 0) and traces a path, where at each time step it flies in one of the four cardinal directions, staying inside the matrix and never returning to an already-visited square. It eventually stops on some square. The entries of the matrix are as follows:

A[i,j] = NULL if the bird never visited A[i,j].

A[i,j] = RIGHT if the bird visited A[i,j] and then flew to the square to the right.

(similarly for UP, DOWN, LEFT)

A[i,j] = BIRD if the bird stops at that square.

Is there an efficient algorithm to find BIRD?

Answer 1

EDIT: The original posted version (bisecting by rows and columns alternating) with O(N) is not giving the correct answer in all cases - as pointed out by @Pychopath . When only bisecting the rows the algorithm works but is O(N log N). But there is still an O(N) algorithm possible:

By scanning two adjacent rows (or columns) one can count the number of crossings of the bird's path in both directions with the line between the rows (columns). When we know the side on which the path starts we can decide on which side the path ends.

Given a rectangle (sub-matrix) we know if the path starts inside by checking if (0,0) is inside the rectangle. Scanning along all four sides for crossings in and out we can decide if the path ends inside or outside the rectangle.

If we know that the path ends inside a given square with side n (lets assume n is even) we can divide it into 4 squares of equal size and find the one where the path ends - with at most 2*3*2*n = 12n queries (sides lying on the border of the original matrix would need no crossing counts, but this is not exploited here).

Lets assume that N is a power of 2 (if not we can replace it by the next power of 2). Then with each step we can halve the size of the square where we know that the path must end.

Altogether we have a maximum of roughly 12N + 12N/2 + 12N/4 + ... = 24N queries.

Here is Python code:

O,L,R,U,D,B = range(6) # NULL, LEFT, RIGHT, UP, DOWN, BIRD
M = [
[R,R,D,O,O,O,O,O,O,O], # path starts at (0,0), i.e. top left corner
[O,O,D,O,R,R,D,O,O,O],
[O,O,D,O,U,O,D,O,O,O],
[D,L,L,O,U,O,D,O,O,O],
[R,R,R,R,U,O,D,B,L,O], # path ends at 'B'
[O,O,O,O,O,O,D,O,U,O],
[O,D,L,L,L,L,L,O,U,O],
[O,D,O,O,O,O,O,O,U,O],
[O,D,O,R,R,D,O,O,U,O],
[O,R,R,U,O,R,R,R,U,O]
]

def getMatrixEntry(rowIdx, colIdx):
  if rowIdx < 0 or rowIdx >= len(M):         return O
  if colIdx < 0 or colIdx >= len(M[rowIdx]): return O
  return M[rowIdx][colIdx]

# given a rectangular range in which the path ends,
# find the quadrant in which the path ends
def getQuadrantOfPathEnd(rowStart, rowEnd, colStart, colEnd):
  if rowEnd - rowStart <= 4 or colEnd - colStart <= 4:
    # just scan for B
    for rowIdx in range(rowStart, rowEnd):
      for colIdx in range(colStart, colEnd):
        if getMatrixEntry(rowIdx, colIdx) == B:
          return rowIdx,rowIdx+1,colIdx,colIdx+1
    assert False, f"path end expected inside {(rowStart, rowEnd, colStart, colEnd)}, but not found"

  # split rectangle into quadrants at center row and column
  # (quadrants are indexed in matrix like fashion [0][0], [0][1], [1][0], [1][1] )
  rowSplit = (rowStart + rowEnd) // 2
  colSplit = (colStart + colEnd) // 2
  # lets scan the horizontal borders of the quadrants for vertical crossings
  # (the six border lines at top left, top right, center left, center right, bottom left, bottom right
  # are indexed in matrix like fashion)
  # The crossing sums are 
  # - incremented for each crossing from top to bottom and 
  # - decremented for each crossing from bottom to top
  vertCrossSums = []
  for rowIdx in [rowStart-1, rowSplit-1, rowEnd-1]:
    vertCrossSumLeft = 0
    for colIdx in range(colStart, colSplit):
      if getMatrixEntry(rowIdx,colIdx) == D:
        vertCrossSumLeft += 1
      if getMatrixEntry(rowIdx+1,colIdx) == U:
        vertCrossSumLeft -= 1
    vertCrossSumRight = 0
    for colIdx in range(colSplit, colEnd):
      if getMatrixEntry(rowIdx,colIdx) == D:
        vertCrossSumRight += 1
      if getMatrixEntry(rowIdx+1,colIdx) == U:
        vertCrossSumRight -= 1
    vertCrossSums.append((vertCrossSumLeft, vertCrossSumRight))
  # lets scan the vertical borders of the quadrants for horizontal crossings
  # (the six border lines at top left, top center, top right, bottom left, bottom center, bottom right
  # are indexed in matrix like fashion)
  # The crossing sums are 
  # - incremented for each crossing from left to right and 
  # - decremented for each crossing from right to left
  horCrossSums = []
  for colIdx in [colStart-1, colSplit-1, colEnd-1]:
    horCrossSumTop = 0
    for rowIdx in range(rowStart, rowSplit):
      if getMatrixEntry(rowIdx,colIdx) == R:
        horCrossSumTop += 1
      if getMatrixEntry(rowIdx,colIdx+1) == L:
        horCrossSumTop -= 1
    horCrossSumBottom = 0
    for rowIdx in range(rowSplit, rowEnd):
      if getMatrixEntry(rowIdx,colIdx) == R:
        horCrossSumBottom += 1
      if getMatrixEntry(rowIdx,colIdx+1) == L:
        horCrossSumBottom -= 1
    horCrossSums.append((horCrossSumTop, horCrossSumBottom))
  print("  vertical   crossing sums", vertCrossSums)
  print("  horizontal crossing sums", horCrossSums)

  # lets find the quadrant where the path ends
  for subVertIdx in range(2):
    for subHorIdx in range(2):
      quadrant = (
        [rowStart, rowSplit][subVertIdx],
        [rowSplit, rowEnd]  [subVertIdx],
        [colStart, colSplit][subHorIdx],
        [colSplit, colEnd]  [subHorIdx]
      )
      pathStartsInside = 1 if quadrant[0] == 0 and quadrant[2] == 0 else 0
      # sum the crossings along the 4 borders of a quadrant
      # (+1 for each crossing going into, -1 for each crossing going out of the quadrant)
      quadrCrossSum = (
        vertCrossSums [subVertIdx][subHorIdx] - vertCrossSums [subVertIdx+1][subHorIdx] +
        horCrossSums[subHorIdx][subVertIdx] - horCrossSums[subHorIdx+1][subVertIdx]
      )
      pathEndsInside = pathStartsInside + quadrCrossSum
      assert 0 <= pathEndsInside <= 1, f"pathEndsInside {pathEndsInside} = {pathStartsInside} + {quadrCrossSum} not in [0,1] for {quadrant}"
      if pathEndsInside == 1:
        return quadrant
  assert False, "quadrant with path end inside expected, but not found"

# rectangle with path end inside
rTop,rBot,rLft,rRgt = 0,len(M),0,len(M[0])
while rBot-rTop > 1 or rRgt - rLft > 1:
  print("rectangle", (rTop,rBot,rLft,rRgt))
  rTop,rBot,rLft,rRgt = getQuadrantOfPathEnd(rTop,rBot,rLft,rRgt)
assert M[rTop][rLft] == B
print("bird at", rTop,rLft)

giving the following output:

rectangle (0, 10, 0, 10)
  vertical   crossing sums [(0, 0), (0, 0), (0, 0)]
  horizontal crossing sums [(0, 0), (1, 0), (0, 0)]
rectangle (0, 5, 5, 10)
  vertical   crossing sums [(0, 0), (1, 0), (1, -1)]
  horizontal crossing sums [(1, 0), (0, 0), (0, 0)]
rectangle (2, 5, 7, 10)
bird at 4 7