1333: 小鼠迷宫问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：174
解决：43
题目描述
小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的（p，q）方格中，它必须找出一条通向小鼠b所在的（r，s）方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。
任务：对于给定的小鼠的迷宫，请你编写一个程序来计算小鼠a通向小鼠b的所有最短道路。
输入
第一行为三个正整数n，m，k（1<=n，m<=100，0<=k<=m×n-2），分别表示迷宫的行数，列数和封闭的房间数。
接下来的k行，每行有两个正整数，表示被封闭的房间所在的行号和列号。
最后的两行，每行有两个正整数，分别表示小鼠a所处的方格（p，q）和小鼠b所处的方格（r，s），小鼠a和小鼠b所处的方格是不封闭的。
接下来的k行，每行有两个正整数，表示被封闭的房间所在的行号和列号。
最后的两行，每行有两个正整数，分别表示小鼠a所处的方格（p，q）和小鼠b所处的方格（r，s），小鼠a和小鼠b所处的方格是不封闭的。
输出
为计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路。
第一行中为最短路长度。
第二行中为不同的最短路数。
如果小鼠a无法通向小鼠b，则输出“No Solution!”（不含引号）。
第一行中为最短路长度。
第二行中为不同的最短路数。
如果小鼠a无法通向小鼠b，则输出“No Solution!”（不含引号）。
样例输入 复制
8 8 3
3 3
4 5
6 6
2 1
7 7
样例输出 复制
11
96