You are trapped in a grid where some cells contain walls, some are occupied by zombies, and others are open paths. Your goal is to find the shortest path from the start point to the gate (exit), while staying as far away from the zombies as possible.
Grid Details:
The grid is represented as a 2D matrix.
Each cell in the matrix can be one of the following:
'S': Start position (You begin at this location).
'G': Gate (Your goal is to reach this location).
'Z': Zombie (You should avoid these cells as much as possible).
'W': Wall (These cells are impassable).
'0': Open cell (You can move through these cells).
Movement:
You can move up, down, left, or right, but cannot move diagonally.
You cannot move through walls.
Your priority is to stay as far away from zombies as possible while still finding the shortest path to the gate.
Task:
Write a function that takes this matrix as input and returns the path so you stay as far as possible from zombie.
Similar to https://leetcode.com/problems/find-the-safest-path-in-a-grid/description/ but without walls.
