在一个n*m的迷宫里,每一个坐标点有两种可能:0或1,0表示该位置允许通过,1表示该位置不允许通过.
如地图: 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 最短路径应该是 AB000 1C101 ED111 F1JKL GHI1M 即: (1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5) 由input.txt中输入一个迷宫,以坐标的方式输出从左上角到右下角的最短路径. 如: input(from input.txt): 5 5 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 output (to screen): (1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5) input: 5 5 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 output: There is no way to leave! 算法分析: 如示例地图: 00000 10101 00111 01000 00010 我们可知,点[5,5]到点[5,5]的距离为0(废话) 因此,我们把该位置标志为0, 点[4,5]到点[5,5]的距离为点[5,5]到点[5,5]的距离+1,也即1. 点[4,4]到点[4,5]的距离至多为点[4,5]到点[5,5]的距离+1,因为点[4,4]可以直接到达点[4,5],所以点[4,4]到点[5,5]的距离为2; . . . . 点[1,1]到点[5,5]的距离为12,并且可以证明是最短距离. 此时,由于点[1,1]到点[5,5]的距离为12,且点[1,2]到点[5,5]的距离为11,我们便可以知道,从点[1,1]到点[1,2],一定是更接近点[5,5]而不是更远离,接下去我们找点[1,2]周围距离为10的,[1,3]周围距离为9的......直到找到[5,5],我们找到的就是最短路径. 算法用C语言表示大致如下:
|
