Squares in Movement Range

Question

There are two inputs, the first input is a map in 2D array, where 2 represents an obstacle and 0 represents a regular ground, and 1 represents the player's location (implies that the player is standing on ground), the second input is the player's movement range.

A player can move on the map (horizontally, vertically, but not diagonally) within the movement range (0 to movement range inclusive), and the player can travel through an obstacle, but only one at a time. At last, a player cannot stand on an obstacle.

The program outputs an 2D array of booleans, showing all possible squares the player can move to.

Here are some examples:

Input

________
_____#__
___+__#_
#__#____
________, range=2
(_ = 0, + = 1, # = 2)

Output

___+____
__+++___
_+++++__
__+_+___
___+____ (+ = true, _ = false)

Input

__________
__________
______#___
__#_+##___
__________
____#_____
__________, range=4

Output

___+++____
__+++++___
_+++++_+__
++_++_____
_+++++++__
__++_++___
___+++____

There will be two winners: shortest brute-force and shortest efficient algorithm (the map and the movement range can get arbitrarily large)

Answer 1

Python, 284 characters

def M(A,R):
 X,Y=range(len(A[0])),range(len(A))
 G,P,H=[set(x+1j*y for x in X for y in Y if A[y][x]>=z) for z in(0,1,2)]
 P-=H
 for i in' '*R:P|=G&reduce(lambda x,y:x|y,[set(p+d for p in P)-(H&set(p+d for p in H))for d in(1,1j,-1,-1j)])
 return[[x+1j*y in P-H for x in X]for y in Y]

def display(A):print'\n'.join(''.join('_+'[c]for c in r)for r in A)

A=[[0,0,0,0,0,0,0,0],
   [0,0,0,0,0,2,0,0],
   [0,0,0,1,0,0,2,0],
   [2,0,0,2,0,0,0,0],
   [0,0,0,0,0,0,0,0]]
display(M(A,2))

A=[[0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,2,0,0,0],
   [0,0,2,0,1,2,2,0,0,0],
   [0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,2,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0]]
display(M(A,4))

The main M routine takes the 2D array containing the map and the range, and returns the 2D array of booleans.

G is the set of all indexes of (in-bounds) squares, encoded as complex numbers. H is the same but for the obstacles, and P is the same for the player. The main loop updates P by moving P in each of the 4 cardinal directions, filtered by the obstacles and the bounds of the array.