[Question]
  [
## Task
* Print 0 if an `n*m` maze cannot be solved
* Print 1 if an `n*m` maze can be solved (in 1 or more ways)
(so I'm not asking for paths but if it's possible to solve!!!)
## Example
Input array(2d):
```
[[0,0,0,0,0,0,1],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0],[1,0,0,0,0,0,0]]
XXXXXXXXX
XS     XX
X     X X
X    X  X
XX     FX
XXXXXXXXX
0 = can pass through
1 = can not pass trough
[0][n] is the last block of the first line
[m][0] is the first block of the last line
```
**Rule**
The start position is 0,0 and the end position is n,m
You can only move horizontally and vertically
Shortest code wins
  
[Answer]
# Dyalog APL, 27 characters
[`⊃⌽∨.∧⍨⍣≡1≥+/¨|∘.-⍨,(~×⍳∘⍴)⎕`](http://tryapl.org/?a=%u2283%u233D%u2228.%u2227%u2368%u2363%u22611%u2265+/%A8%7C%u2218.-%u2368%2C%28%7E%D7%u2373%u2218%u2374%29%20%204%207%u23740%200%200%200%200%200%201%20%200%200%200%200%200%201%200%20%200%200%200%200%201%200%200%20%201%200%200%200%200%200%200&run)
`⎕` evaluated input. APL distinguishes between a matrix and a vector of vectors. This program assumes that the input is a matrix.
`(~×⍳∘⍴)A` is a fork equivalent to `(~A) × ⍳⍴A`. It's needed to avoid mentioning `⎕` twice or introducing a variable.
`⍴A` is the shape of `A`. For a 4-by-7 matrix the shape is `4 7`.
`⍳` is the index generator. `⍳4` is `1 2 3 4`. `⍳4 7` is the vectors `(1 1)(1 2)...(4 7)` arranged in a 4-by-7 matrix.
`~A` flips the bits of `A`.
`×` by multiplying `⍳⍴A` by the flipped bits, we preserve the coordinates of all free cells and turn all walls into `0 0`.
`,` ravels the matrix of coordinate pairs, i.e. linearizes it into a vector. In this case the vector will consist of pairs.
`∘.-⍨A` or `A∘.-A` subtracts elements of `A` pairwise. Note that here the elements of `A` are themselves pairs.
`|` absolute value
`+/¨` sum each pair of absolute values. This gives us the grid distances between every pair of cells in the maze, save for walls.
`1≥` we are only intrested in neighbours at a distance no more than 1, this also excludes walls. Now we have a graph's adjacency matrix.
`∨.∧⍨⍣≡` Floyd--Warshall's transitive closure algorithm
`(f⍣n)A` (not used here) where `n` is an integer is the power operator. It applies `f` to `A` `n` times: `f f ... f A`.
`(f⍣g)A` where `g` is a function, is the fixed point operator, a.k.a. "power limit". It keeps on computing the series `A`, `f A`, `f f A`, ... until `((f⍣i)A) g ((f⍣(i+1))A)` returns true for some `i`. In this case we use match (`≡`) as `g`.
`∨.∧⍨A` or `A∨.∧A` is a step in Floyd's algorithm. `f.g` is a generalisation of matrix multiplication (`+.×`), here we use conjunction (`∧`) and disjunction (`∨`) in place of `+` and `×`.
`⊃⌽` After `⍣≡` has applied the step enough times and reached a stable state, we must look up the top-right corner of the matrix to get the result, so we flip it (`⌽`) and take the first, top-left item (`⊃`).
[Visualization of `⍣≡`'s steps](http://tryapl.org/?a=a%u21904%207%u23740%200%200%200%200%200%201%200%200%200%200%200%201%200%200%200%200%200%201%200%200%201%200%200%200%200%200%200%20%u22C4%20%7B%27.%23%27%5B1+%28%u2374a%29%u2374%u2228.%u2227%u2368%u2363%u2375%u22A21%u2265+/%A8%7C%u2218.-%u2368%2C%28%7E%D7%u2373%u2218%u2374%29a%5D%7D%A8%AF1+%u23736&run)
[Answer]
# CJam, 42 41 39 36 35 bytes
```
Wq3>~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=
```
Based on the ideas in [this answer](https://codegolf.stackexchange.com/a/40204/25180).
4 bytes thanks to Optimizer.
Input format:
```
[[0 0 0 0 0 0 1] [0 0 0 0 0 1 0] [0 0 0 0 1 0 0] [1 0 0 0 0 0 0]]
```
[Answer]
# Python, 164 bytes
```
def s(a):
 d=[(0,0)]
 while d:i,j=d.pop();a[i][j]=2;d+=[(x,y)for x,y in[(i-1,j),(i,j-1),(i+1,j),(i,j+1)]if len(a[0])>y>-1<x<len(a)and a[x][y]<1]
 return a[-1][-1]>1
```
I was reluctant to post this because it's practically how I'd normally do flood fill, just lightly golfed. But here it is anyway.
[Answer]
## Perl, 73 bytes
69 bytes of code + 4 bytes for `-n0E` (not sure how the tags where counted in 2014, so I counted them for 4 instead of 2, but it doesn't matter a lot).
```
/.*/;s/(^0|A)(.{@{+}})?0/A$2A/s||s/0(.{@{+}})?A/A$1A/s?redo:say/A$/+0
```
[Try it online!](https://tio.run/##K0gtyjH9r6xYAKQVdPMMuEqLUxXSUhNLSotSFdSLEyvVrf/r62npWxfra8QZ1DhqauhVO1Rr19Zq2hvoO6oYOeoX19QU6xsghB2BwoZAYfui1JR8K6AJQL6@tsH//wZgYMgFoQy4DIHAwBDKNzAAAA "Perl 5 – Try It Online")
(and if you replace the `1111011` line with `1111111`, the maze isn't solvable anymore, and the output will be `0` instead of `1` : [Try it online!](https://tio.run/##K0gtyjH9r6xYAKQVdPMMuEqLUxXSUhNLSotSFdSLEyvVrf/r62npWxfra8QZ1DhqauhVO1Rr19Zq2hvoO6oYOeoX19QU6xsghB2BwoZAYfui1JR8K6AJQL6@tsH//wZgYMgFoQy4DCEAwjcwAAA "Perl 5 – Try It Online"))
**Explanations:**
This code will find every reachable cell of the maze (and mark them with a `A`): if a cell touches a cell marked with a `A`, the it's reachable and we mark it with a `A` too; and we do that again (`redo`). That's done thanks to two regex: `s/(^0|A)(.{@{+}})?0/A$2A/s` checks if a space is on the right or the bottom of a `A`, while `s/0(.{@{+}})?A/A$1A/s` checks if a space is on the left or on top of a `A`. At the end, if the last cell contains a `A` it's reachable, otherwise it's not (that's what `say/A$/+0` checks; the `+0` is here to make sure the result will be `0` or `1` instead of *empty string* and `1`).  
Note that `/.*/` will match an entire line, thus setting `@+` to the index of the end of the first line, which happens to be the size of a line, which allow use to use `.{@{+}}` to match exactly as many character as there are on a line. (`@{+}` is equivalent to `@+`, but only the former can be used in regex)
[Answer]
# Ruby, ~~133~~ ~~130~~ 129 characters
```
a=eval gets
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o[0],y+o[1]
f[d,e]if a[d]&&a[d][e]==0}}
f[0,0]
p a[-1][-1]
```
Input on STDIN, outputs `1` or `0` on STDOUT.
Annoyingly long. It simply does a flood-fill of `1`s from `(0, 0)`, and then checks to see whether the "end" square is a `1`.
[Answer]
### Java, 418 bytes
```
import java.util.Scanner;public class Solvable{static int w,h;public static void main(String[] a){String[]i=new Scanner(System.in).nextLine().split(";");h=i.length+2;w=i[0].length()+2;int[]m=new int[w * h];for(int x=1;x<w-1;x++)for(int y=1;y<h-1;y++)m[y*w+x]=i[y-1].charAt(x-1)<'.'?0:1;f(m,w+1);System.out.println(m[w*h-w-2]>0?0:1);}static void f(int[]m,int i){if(m[i]>0){m[i]--;f(m,i-1);f(m,i+1);f(m,i-w);f(m,i+w);}}}
```
My first code golf. I don't know why I chose Java - it's so bad for golfing xD
Example maze would be inputted via stdin like this:
```
......#;.....#.;....#..;#......
```
[Answer]
## Python 184 ~~188~~
```
def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a[0]),len(a);return([x,y]in h)==(x>=X)==(y>=Y)==(x<0)==(y<0)==a[y][x]<(x==X-1and y==Y-1or f(a,x-1,y,s)|f(a,x+1,y,s)|f(a,x,y-1,s)|f(a,x,y+1,s))
```
This got much longer than I thought it would be :( Anyway, I'll add an explanation once I can't golf it any longer.
[Answer]
## J, 75 chars
Powering of the adjacency matrix (very time and memory inefficient). *(Is it called powering in English?)*
```
   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:)))
```
Some test cases:
```
   m1=. 0 0 0 0 0 0 1,. 0 0 0 0 0 1 0,.  0 0 0 0 1 0 0,. 1 0 0 0 0 0 0
   m2=. 0 1 1 ,. 0 0 0
   m3=. 0 1 0 ,. 1 1 0
   m4=. 0 1 1 0 ,. 0 0 1 0
   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:))) every m1;m2;m3;m4
1 1 0 0
```
[Answer]
# [Python 3](https://docs.python.org/3/), 136 bytes
```
def f(g,x=0,*p):w=len(g[0])+1;l=w*len(g);return~x%w*(-1<x<l)*~-(x in p)and any(g[x//w][x%w]and f(g,x+a,*p,x)for a in(1,-1,w,-w))or-~x==l
```
[Try it online!](https://tio.run/##tY/NCoMwEITvPkUuhawmmNBba55Ecgj4U0GiBEvixVe3qUX7k4K9NHPa4cvsbD8Ol04f57koK1ThmjjBSNzDyYq21LjOmYSEn1th42WGsymHq9GTO9gYU565rIV4otihRqMelC6Q0qP/6NLUytxj8u4t0Yny0cRB1RmkPI85oZxYQi1AZ@jkhGjn3jR6wBXOc064JBFa3zJLgCh6Rdg@8p7CQoT9sugTYXtd2NeUTUHx1Q/LrH54yVP/XvXQtmq@AQ "Python 3 – Try It Online")
Uses `0` for wall, `1` for free space.
Port of my answer to [Find the shortest route on an ASCII road](https://codegolf.stackexchange.com/a/195042/87681).
[Answer]
# [Python 3](https://docs.python.org/3/), 184 bytes
```
f=lambda m,x=0,y=0,n=0:n<len(m)*len(m[0])and m[x][y]<1and((x,y)==(len(m)-1,len(m[0])-1)or any(0<=i<len(m)and 0<=j<len(m[0])and f(m,i,j,n+1)for i,j in[(x-1,y),(x,y-1),(x+1,y),(x,y+1)]))
```
[Try it online!](https://tio.run/##jZBBCsIwEEX3niLLiY6QwZ00JwlZVLRYMaOULpLT16m1NbYKUtLJhzfvQ@6pPd9413WVvZbhcCxVwGgNJjlszZ6L64kh6PVzOON1yUcVXPQu@YIkAERM2loYwC3hhG5J3xpVcgJT2Ppl6vclXooPYwUBa7wgb0hXsiR3VbODKL6kse8Qm8zNlIX0Wnf3puYWKnDO4Psjj1kmNFmm/i@ZMt54ca1mrnFnmktm6KG3b8HQzEMLhv7smjP0rSvvmbp/3ce36d/xAQ "Python 3 – Try It Online")
]