A183.Gold King勇闯八卦图4

普及+/提高

官方

通过率:67.97%

时间限制:1.00s

内存限制:128MB

题目描述

冬季的青青草原,千里冰封,万里雪飘,前往八卦图的道路困难至极。

Gold King 的鸡血完全被激发出来,上次知道的那条最短路线被冰封了,这次想把所有最短路线输出显示。于是 Gold King 来到了八卦图入口,得知八卦图的规模 nnmm 列,由 0 构成的可以走的路,由 1 构成的墙壁,可以沿下右上左四个方向移动。试着根据给定的入口和出口,输出 Gold King 走出八卦图的最短路径步数和所有最短路线。

输入格式

第一行输入整数 TT 表示有 TT 组测试数据。
接下来 TT 组测试数据:
每组第一行输入两个整数 nnmm,表示八卦图规模 nnmm 列。
接下来 nn 行每行输入 mm 个空格隔开的数字,表示八卦图信息。0 表示路,1 表示墙壁,2 表示入口,3 表示出口。

输出格式

对于每组测试数据输出所有的最短路线方案。
一行输出一个方案,每个最短路线方案以 <a>- b:x1,y1-->x2,y2-->x3,y3 的形式输出,其中 aa 表示最短路径步数,bb 表示当前测试数据的最短路线方案编号(从1开始),后面输出从起点 x1,y1x1,y1 到终点 x3,y3x3,y3 中间每一步的路径信息。

输入输出样例

  • 输入#1

    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 0 0 0
    1 0 1 1 0
    0 0 1 0 0
    0 1 1 0 1
    0 0 0 0 3

    输出#1

    <9>- 1:0,0-->1,0-->2,0-->3,0-->4,0-->4,1-->4,2-->4,3-->4,4
    <9>- 2:0,0-->1,0-->2,0-->2,1-->2,2-->2,3-->2,4-->3,4-->4,4
    <9>- 3:0,0-->0,1-->0,2-->1,2-->2,2-->2,3-->2,4-->3,4-->4,4
    <9>- 4:0,0-->0,1-->0,2-->0,3-->0,4-->1,4-->2,4-->3,4-->4,4
    <11>- 1:0,0-->0,1-->1,1-->2,1-->2,0-->3,0-->4,0-->4,1-->4,2-->4,3-->4,4
    <11>- 2:0,0-->0,1-->0,2-->0,3-->0,4-->1,4-->2,4-->2,3-->3,3-->4,3-->4,4
首页