Knock down walls in a maze Rules:

In this game you start at the top of a rectangular grid of size N x M made up of walls and open spaces. The input is N lines of M characters, where a . specifies an open space and a x specifies a wall. Your program should output the smallest number K such that there exists a path from the top left corner to the bottom right corner (no diagonals) that crosses K walls.

For example, given the input:

..x..
..x..
xxxxx
..x..
..x..


your program should output 2.

Other examples:

output 4:

xxxxx
x.x.x
x.x.x
x..xx


output 0:

.xxxxxxxx
.x...x...
.x.x.x.x.
.x.x...x.
...xxxxx.


output 6:

xx
xx
xx
xx
xx


Extra tidbits:

If it makes your life easier, you can specify N and M as command line parameters.

Extra credit if you can have your program print out the path in some form or another.
Ruby 1.9 (235) (225) (222) (214)

I don't know if this is shorter than a program based on Dijkstra, but I figured I would try a different approach. This uses regex in a loop to mark each space with the minimal number of walls required to reach it.

w=".{#{/\s/=~s=$&lt;.read}}?"
j="([.x])"
s[0]=v=s[0]&lt;?x??0:?1
(d=v[-1];n=v.succ![-1]
0while(s.sub!(/#{j}(#{w+d})/m){($1&lt;?x?d: n)+$2}||s.sub!(/(#{d+w})#{j}/m){$1+($2&lt;?x?d: n)}))while/#{j}/=~q=s[-2]
p v.to_i-(q==n ?0:1)


Input is specified as a file on the command line, i.e.

&gt; ruby1.9.1 golf.rb maze.txt


Ungolfed:

# read in the file
maze = $&lt;.read

# find the first newline (the width of the maze)
width = /\s/ =~ maze

# construct part of the regex (the part between the current cell and the target cell)
spaces = ".{#{width}}?"

# construct another part of the regex (the target cell)
target = "([.x])"

# set the value of the first cell, and store that in the current wall count
maze[0] = walls = (maze[0] == "x" ? "1" : "0")

# loop until the goal cell is not "." or "x"
while /#{target}/ =~ (goal = s[-2])

  # store the current wall count digit and the next wall count digit, while incrementing the wall count
  current = walls[-1]; next = walls.succ![-1]

  # loop to set all the reachable cells for the current wall count
  begin

    # first regex handles all cells above or to the left of cells with the current wall count
    result = s.sub!(/#{target}(#{spaces + current})/m) {
      ($1 == 'x' ? next : current) + $2
    }

    # second regex handles all cells below or to the right of cells with the current wall count
    result = result || s.sub!(/(#{current + spaces})#{target}/m) {
      $1 + ($2 == 'x' ? next : current)
    }
  end while result != nil
end

# we reached the goal, so output the wall count if the goal was a wall, or subtract 1 if it wasn't
puts walls.to_i - (goal == next ? 0 : 1)