Programmers / Shortest Path in Game Map

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

import java.util.LinkedList;

class Solution {
    public int solution(int[][] maps) {
        // Get map size
        int mapX = maps.length;
        int mapY = maps[0].length;
        System.out.printf("mapX:%d, mapY:%d", mapX, mapY);
        
        // Init vars
    	  boolean[][] visitedMap = new boolean[mapX][mapY];
        LinkedList<Position> nextQueue = new LinkedList<>();
        
        // Find path
        visitedMap[0][0] = true;
        nextQueue.offer(new Position(0, 0, 1));
        while(nextQueue.size() != 0) {
            // Get next position
            Position nextPos = nextQueue.poll();
            int nextX = nextPos.getX();
            int nextY = nextPos.getY();
            int nextDepth = nextPos.getDepth();
            
            // Check this position is goal
           	if (nextX == mapX - 1 && nextY == mapY - 1) {
                return nextDepth;
            }
            
            // Enqueue next position to visit
            if ((nextX+1 < mapX) && (maps[nextX+1][nextY] == 1) && (!visitedMap[nextX+1][nextY])){
                visitedMap[nextX+1][nextY] = true;
                nextQueue.offer(new Position(nextX+1, nextY, nextDepth+1));
            } 
            if ((nextY+1 < mapY) && (maps[nextX][nextY+1] == 1) && (!visitedMap[nextX][nextY+1])){
                visitedMap[nextX][nextY+1] = true;
                nextQueue.offer(new Position(nextX, nextY+1, nextDepth+1));
            } 
            if ((nextX-1 >= 0) && (maps[nextX-1][nextY] == 1) && (!visitedMap[nextX-1][nextY])){
                visitedMap[nextX-1][nextY] = true;
                nextQueue.offer(new Position(nextX-1, nextY, nextDepth+1));
            } 
            if ((nextY-1 >= 0) && (maps[nextX][nextY-1] == 1) && (!visitedMap[nextX][nextY-1])){
                visitedMap[nextX][nextY-1] = true;
                nextQueue.offer(new Position(nextX, nextY-1, nextDepth+1));
            }
        }
        
        // Not reachable
        return -1;
    }
}

class Position {
    public int x;
    public int y;
    public int depth;
    
    public Position(int x, int y, int depth) {
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
    
    public int getX() {
        return x;
    }
    
    public int getY() {
        return y;
    }
    
    public int getDepth() {
        return depth;
    }
}