问题说明

青青草原上神奇的八卦图，每一格的移动，会产生“蝴蝶效应”。
Gold King觉得这样才有挑战性，上次知道了最少几步就能走出来，这次想把这个最短路径输出显示。于是Gold King来到了八卦图入口，得知八卦图的规模n行m列，由0构成的可以走的路，由1构成的墙壁，可以沿下右上左四个方向移动。试着根据给定的入口和出口，输出Gold King走出八卦图的最短路径步数和最短路线。

输入格式

第一行输入整数T表示有T组测试数据。
第二行输入两个整数n和m，表示规模n行m列。 接下来输入八卦图信息。0表示路，1表示墙壁，2表示入口，3表示出口。

输出格式

对于每组测试数据输出两行数据，第一行输出最短路径步数，第二行输出一条最短路线。

2
5 5
2 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 3
5 5
2 0 1 0 0
1 0 0 1 0
0 0 1 0 0
0 1 1 1 0
0 0 0 0 3

9
(0,0)-->(1,0)-->(2,0)-->(3,0)-->(4,0)-->(4,1)-->(4,2)-->(4,3)-->(4,4)
11
(0,0)-->(0,1)-->(1,1)-->(2,1)-->(2,0)-->(3,0)-->(4,0)-->(4,1)-->(4,2)-->(4,3)-->(4,4)

提示

2<=n<=110
2<=m<=110
Gold King从起点出发已经有一步了。

来源/分类

算法培训-17-广度优先搜索