# Java A* Search solution.

• Instead of finding the maximum vocation days, we can convert the question into finding the minimum work days.
For example, if the vocation days of a week is 1, then the work days is `7-1=6`.
Therefore, A* search can be applied to solve this problem.
The vocation days is `( 7 * K ) - min(work days)`.

``````public class Solution {
class WeekLoc {
int week, city, workday;
int key;
WeekLoc(int week, int city) {
this.week = week;
this.city = city;
key = (city * 100) + week;
workday = 0;
}
}
class WeekLocComp implements Comparator<WeekLoc> {
public int compare(WeekLoc w1, WeekLoc w2) {
return w1.workday - w2.workday;
}
}
public int maxVacationDays(int[][] flights, int[][] days) {
int N = flights.length, K = days[0].length;
PriorityQueue<WeekLoc> queue = new PriorityQueue(1, new WeekLocComp());
Set<Integer> visited = new HashSet<>();
queue.offer(new WeekLoc( -1, 0 ));
while (! queue.isEmpty() ) {
WeekLoc cur = queue.poll();
//System.out.println("week:"+cur.week+" city:"+cur.city + " day:" + cur.workday );
if (cur.week == K-1) return 7*K - cur.workday;
for (int i = 0 ; i < N; i++) {
if ( i == cur.city || flights[cur.city][i] == 1 ) {
WeekLoc next = new WeekLoc(cur.week+1, i);
if (! visited.contains(next.key) ) {
next.workday = cur.workday + ( 7 - days[next.city][next.week]);
queue.offer(next);
}
}
}
}
return 0;
}
}
``````

• Is it necessary to treat it as A*? It's a simple BFS.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.