1491: 风暴机器人
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：56
解决：43
题目描述
最近嵌入式工作室引进了一批“风暴”系列机器人，它们全身都装满了传感器，如光敏传感器、烟雾传感 器、红外传感器等。因此，它们看起来是那么的智能，当它们在地面行走时，如果前方有障碍物，它就 会换个方向尝试是否可以行走。为了简化编程，我们把机器人看作在一个N*M的网格中行走，且机器人只 能沿上、下、左、右四个方向行走，在这N*M的网格中，我们在其中L个网格上放障碍物，放有障碍物的 格子表示机器人不能通过这个表格。机器人起始时位于网格a(p, q)中，它必须找出一条通向目的地b(r, s)的路。现在，请你帮助这个“风暴”机器人找出所有路径中的最短路径吧。
输入
本题有多组输入数据，你必须处理到EOF为止。 每组数据的第一行有3个正整数N，M，L，(2<=N,M<=10, 0<=L<=10)分别表示网格的行数，列数和障碍物 数。接下来的L行中，每行2个正整数，表示障碍物所在的行号和列号(行列号从1开始)。最后的2行，每 行也有2个正整数，分别表示起始位置a所处的方格(p, q)和目的地b所处的方格(r, s)。(1≤p,r≤n; 1≤q,s≤m; a,b两点确保不同)。
输出
对于每组数据，如果机器人能从起始位置a行走到目的地b，则输出两行，第一行表示最短路长度；第二行表示所有不同的最短路数。如果机器人不能从起始位置a行走到目的地b，输出“No Solution!”(不包括引号)。
样例输入 复制
8 8 3
3 3
4 5
6 6
2 1
7 7
2 2 2
1 2
2 1
1 1
2 2样例输出 复制
11
96
No Solution!提示
队列