Sunday Morning Date
InterviewTime limit2sMemory limit128 MB
Find a grid path from S to F that first minimizes the number of trash cells stepped on, then minimizes clean cells adjacent to trash along that path.
- Level
Medium5 of 10
- Topics
- Shortest path, BFS, Graph, Matrix
- Solved
- No attempts yet
Problem
On a Sunday morning, Hyungtaek and his girlfriend decide to walk through a nearby forest and visit a beautiful flower hidden deep inside it. Unfortunately, some people have left trash in the forest.
Hyungtaek has learned two things during their relationship: his girlfriend really dislikes stepping on trash, and she is also uncomfortable walking right next to trash.
You are given a map of the forest. S is the starting point of the date, F is the flower, g is a cell containing trash, and . is a clean empty cell.
They need to move from S to F. In one move, they may move one cell up, down, left, or right. First, minimize the number of trash cells they step on. If several paths have that same minimum, choose one that minimizes the number of clean cells adjacent to trash. A clean cell is adjacent to trash if it shares an edge with a trash cell. The S and F cells are not counted as clean cells adjacent to trash.
Input
The first line contains two integers N and M, the height and width of the forest.
3 <= N, M <= 50
The next N lines contain the map of the forest. Each character is one of S, F, g, or ..
There is exactly one S and exactly one F. S is on the boundary of the forest, and F is not on the boundary.
Output
Print two integers separated by a space: the minimum number of trash cells on an optimal path, and then the minimum number of clean cells adjacent to trash among paths with that trash-cell count.