Could anyone got AC help verify this: There will always be a non-zero probability that a generated maze will be solvable.

I write a program that do this thing:
1. read case
2. make a maze, a sqaure has berrier on it only if the input probability is 1.0
3. use BFS to find a route from top left to bottom right
My program found that there is no route on this maze......
Could anyone verify this? Do I make a silly mistake???

My signature:

Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.

Hmm. Looks like requests for a hint are not honoured for this problem... but I'll give it a try.

I've been struggling with this one for over three years now, and I'm getting nowhere. The only thing I can think of is enumerating all possible states and then check if they're connected. This gives me the correct answers, but way too slow. There are some minor optimizations, but none enough to get there in time.

I've used dynamic programming. Subproblems look like this: given that I've generated top the k rows, and knowing which of the cells of the k-th row are connected between them by paths in upper rows (there are not too much possible patterns here), with what probability can I generate the remaining rows such that the maze will be solvable?

There was recently a similar problem on TopCoder - CheapestIsland, you might find its analysis very useful.