hzCPPOJ

走迷宫3

时间限制:  1 s      内存限制:   128 MB
提交:49     正确:31     分值:95

题目描述

假设有一个网格迷宫,由n行m列的单元格构成,每个单元格要么是空地,用“.”表示,要么是障碍物,用“*”表示。

给定起点(x0, y0)和终点坐标(x1, y1),探险家从起点出发,输出起点到终点最少需要走几步?你只能走垂直或者水平路线,不能斜着走,每个单元格最多走一遍(1,1)坐标位于左上角,(n,m)位于右下角。

输入

第1行:  6个由空格隔开的整数: n, m,x0, y0, x1, y1(1 <= x0, x1 <= n<=10, 1 <= y0, y1 <= m<=10)

第2到第n+1行:  数据的第n+1行由m个字符(" ." 表示空地," *" 表示障碍物),描述迷宫的 第n行。

输出

输出一个整数p,从起点到终点最少需要走几步,

接下来p行,按先后顺序输出每一个经过的坐标

样例

样例输入:
3 5 1 1 3 5 .*... .*.*. ...*.
样例输出:
10 1 1 2 1 3 1 3 2 3 3 2 3 1 3 1 4 1 5 2 5 3 5
样例输入:
3 5 1 1 3 5 .*... .*... ...*.
样例输出:
8 1 1 2 1 3 1 3 2 3 3 2 3 2 4 2 5 3 5

提交人

lixun2017

来源/分类