@syb3181 the solution is two fold, first create a graph with its weight being the number of empty cells passed through, and then invoke SPFA on the weighed graph.

Several Tips about SPFA:

the queue contains at most one copy of each node, when it is popped, use the current best solution for that node, so that we needn't put the solution with node into the queue
circled queue can be introduced to reduce the space cost, though in my opinion, it is needless