Grid Route Around Unsafe Cells
A training area is laid out on a 6 by 6 grid. Columns are labelled A-F west to east; rows 1-6 south to north. Start is at A1; objective is at F6. Cells C2, C3, C4, D4, E4, and B5 are marked unsafe. Movement is allowed north, east, south, or west one cell at a time; diagonal movement is not allowed. A route must avoid unsafe cells and cannot pass through the same cell twice. The direct route east along row 1 then north along column F crosses no unsafe cells, but column F has a low-clearance obstacle between F4 and F5: clearance is 3.0 m, and the vehicle is 3.2 m high. The alternate route must go around the unsafe block. You need the shortest safe route in number of moves and a decision about whether to use the low-clearance column. The commander also wants to know whether raising the obstacle clearance would change the shortest distance.
1. Find the shortest safe route from A1 to F6 in moves, and list the sequence of cells. Justify why no shorter route exists.
Read the worked answer
A valid shortest route is: A1, A2, A3, A4, A5, A6, B6, C6, D6, E6, F6. That is 10 moves. It avoids the unsafe cells C2, C3, C4, D4, E4, and B5, and it does not use the blocked F4-F5 edge.
The justification is a lower bound. Any route from A1 to F6 must increase the column by five steps (A to F) and increase the row by five steps (1 to 6). With only north, east, south, and west moves, the minimum possible number of moves is 5 + 5 = 10. The listed route achieves 10 while avoiding all unsafe cells, so it is shortest. The route goes up column A to avoid the unsafe block, then crosses row 6. It cannot simply go east along row 5 because B5 is unsafe and blocks the direct crossing from the A column to the C column at that row.
2. Test the direct route along row 1 then column F. Is it valid? If the clearance were 3.5 m, how would your answer change?
Read the worked answer
The direct route would be A1, B1, C1, D1, E1, F1, F2, F3, F4, F5, F6. It has 10 moves and avoids all unsafe cells, but it is not valid as stated because the F4-F5 edge has 3.0 m clearance while the vehicle is 3.2 m high. The vehicle cannot pass that edge.
If the clearance were 3.5 m, the edge would be usable and the direct route would become valid. Its length is still 10 moves, which is the Manhattan lower bound, so the shortest distance would not change: it would remain 10. The difference would be that there would now be at least two shortest routes, one via column A and row 6 and one via row 1 and column F. The commander should not expect a shorter distance from raising the clearance; the benefit is route flexibility and less dependence on a single corridor.
3. If the clearance is raised and both 10-move routes are available, compare them by exposure to cells adjacent to unsafe cells and recommend one.
Read the worked answer
For the column-A route, the cells adjacent to unsafe cells are A5, which borders B5, and B6, which also borders B5. The rest of the route is not adjacent to an unsafe cell. Exposure count: 2.
For the row-1/column-F route, C1 borders C2, and F4 borders E4. Exposure count: 2. On this simple adjacency measure the routes tie. The recommendation should therefore rest on a secondary factor. I would recommend the column-A/row-6 route even after the clearance is raised, because it does not depend on the low-clearance edge at all. That preserves margin if the clearance measurement is wrong or if the vehicle load shifts. The row-1/column-F route is shorter in travel time only if the clearance is confirmed and the obstacle does not create a delay. If the commander values a direct line and the clearance is verified at 3.5 m, either route is defensible, but the column-A route is the more robust choice under uncertainty.