Shortest Path Finding The Shortest Distance Between Two Points Is A Class Of Algorithm Called Pathfinding.. 5 Shortest Path Finding the shortest distance between two points is a class of algorithm called pathfinding. The distance may be a physical distance between two locations (e.g.
driving directions), or something more abstract like the fastest sequence from start to finish of a construction project. Here you will consider a simplied pathfinding problem where the distance is indices in a matrix. Starting with a matrix of -ls, Os and 1s, find the distance of every 0-valued entry to the nearest 1-valued entry, without passing through -ls. For simplicity, being directly next to a 1 is considered a distance of 2. Create a function with the following header: function [filled] = travelDistance (blank) where blank is a two-dimensional array comprised of -ls, Os and ls, and filled is blank modified to the specifications below. To create filled, replace every 0 in blank with its distance to the nearest 1 (starting at 2), traveling along the four major directions (up, down, left and right) without passing through a -1 value. That is to say, all Os that are directly next to a 1 should be changed to a 2, all Os directly next to any new 2s should be changed to 3s, and so on. Spaces with -1 values should be treated as walls and should stay -1. If there is no route from a 0 to a 1 without passing through a -1, it should remain a 0. The ultimate result should be that every 0 that is connected to a 1 is replaced with its distance to the nearest 1. You can assume that the edges of blank always contain a -1. Your function should be able to reproduce the following test case:
| >> m_small m_small = -1 1 1 1 -1 | -1 -1 -1 -1 -1 -1 | -1 oo -1 oo | | -1 0 1 1 0 -1 -1 o -1 -1 -1 -1 1 | -1 0 -1 0 1 0 | -1 -1 -1 -1 -1 -1 1 1 1 10 1 1 1 >> travelDistance (m_small)
ans = -1 -1 -1 -1 -1 -1 -1 _3 _2 -1 _o _o -1 2 1 -1 _9 -1 -1 _3 -1 -1 -1 -1 . 4 -1 2 1 2 -1 -1 -1 -1 -1 Submit the code of this problem in the file travelDistance.m. ܝ ܝ ܝܙ ܝܙ
