Grid Teleportation Traversal

[Lomanu4]

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

TC : vlogv, where v = m*n


class Solution {
public int minMoves(String[] matrix) {
int m = matrix.length;
int n = matrix[0].length();

int distance[][] = new int[m][n];
for(int v[]: distance){
Arrays.fill(v,Integer.MAX_VALUE);
}

Set<String> set = new HashSet<>();// to keep track of distance teleportation cells
Map<String,List<int[]>> map = new HashMap<>(); // teleportation cells for a given cell [A-Z]
for(int i =0;i< m;i++){
for(int j = 0;j<n;j++){
String str = String.valueOf(matrix.charAt(j));
if(isChar(str)){
map.putIfAbsent(str, new ArrayList<>());
map.get(str).add(new int[]{i,j});
}
}
}

int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
// we have to use dijkstras because the teleportation keeps the moves same
Queue<Tuple> q = new PriorityQueue<>((a,b)-> Integer.compare(a.c, b.c));
distance[0][0] = 0;//initial distance
q.add(new Tuple(0,0,0));
while(!q.isEmpty()){
Tuple t = q.remove();
if(t.i == m-1 && t.j == n-1) return t.c;
String str = String.valueOf(matrix[t.i].charAt(t.j));
if(isChar(str) && !set.contains(str)){
set.add(str);
for(int c[] : map.get(str)){
if(distance[c[0]][c[1]] > t.c){
distance[c[0]][c[1]] = t.c;
q.add(new Tuple(c[0],c[1],t.c));
}
}
}
for(int dir[] : dirs){
int i = t.i + dir[0];
int j = t.j + dir[1];

if(i<m && j<n && i>=0 && j>=0 && !String.valueOf(matrix.charAt(j)).equals("#")){
if(distance[j] > t.c +1){
distance[j] = t.c + 1;
q.add(new Tuple(i,j, t.c+1));
}
}
}
}
return -1;
}
public boolean isChar(String s){
if(s.equals("#") || s.equals(".")) return false;
return true;
}
}
class Tuple{
int i;
int j;
int c;
public Tuple(int i, int j, int c){
this.i = i;
this.j = j;
this.c = c;
}
}

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.