A mouse is trying to get from its starting position S to a treat T, while moving only on land cells and staying as far away as possible from the cat C. Formally, assume again a square grid of size (N x N), allowing only horizontal and vertical moves, impassable cells with water, and cells S, T, and C. We want to find a path from S to T for which the minimal distance to C along the path is maximal. Use the L1 (aka. Manhattan) distance measure, i.e., the sum of the horizontal and vertical distances.

L L W L L
S L C W W
L L L L L
L L L L T