874. 模拟行走机器人

# 874. 模拟行走机器人 (opens new window)

# 1.排序+行列哈希

分析：先将所有障碍按照行列从小到大进行排序，行优先。然后将所有障碍的坐标放入行哈希和列哈希表中。行哈希中key为x坐标值，value为从小到大的y坐标列表。机器人模拟时，因为所有哈希表中的value都进行过排序，因此遍历时遇到的第一个障碍物就是行走过程中会撞上的障碍物。

这里机器人是按照区间来模拟行走，区间满足则一步到位。

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int x=0,y=0;
        int dir=0; // 0向北，1向东，2向南，3向西
        Arrays.sort(obstacles,new Comparator<int[]>(){
                public int compare(int[] o1,int[] o2){
                    if(o1[0]!=o2[0])return o1[0]-o2[0];
                    else return o1[1]-o2[1];
                }
            });
        Map<Integer,List<Integer>> row=new HashMap<>();
        Map<Integer,List<Integer>> line=new HashMap<>();
        for(int i=0;i<obstacles.length;i++){
            if(!row.containsKey(obstacles[i][0])) row.put(obstacles[i][0],new ArrayList<>());
            row.get(obstacles[i][0]).add(obstacles[i][1]);
            if(!line.containsKey(obstacles[i][1])) line.put(obstacles[i][1],new ArrayList<>());
            line.get(obstacles[i][1]).add(obstacles[i][0]);
        }
        int res=0;
        for(int i=0;i<commands.length;i++){
            if(commands[i]==-1) dir=(dir+1)%4;
            else if(commands[i]==-2) dir=dir==0?3:dir-1;
            else{
                //向北走
                if(dir==0){
                    int des=y+commands[i];
                    int pos=des;
                    if(row.containsKey(x)){
                        List<Integer> list=row.get(x);
                        for(int k=0;k<list.size();k++){
                            if(y<list.get(k)&&list.get(k)<=des){
                                pos=list.get(k)-1;
                                break;
                            }
                        }
                    }
                    y=pos;
                }
                //向东走
                if(dir==1){
                    int des=x+commands[i];
                    int pos=des;
                    if(line.containsKey(y)){
                        List<Integer> list=line.get(y);
                        for(int k=0;k<list.size();k++){
                            if(x<list.get(k)&&list.get(k)<=des){
                                pos=list.get(k)-1;
                                break;
                            }
                        }
                        
                    }
                    x=pos;
                }
                //向南走
                if(dir==2){
                    int des=y-commands[i];
                    int pos=des;
                    if(row.containsKey(x)){
                        List<Integer> list=row.get(x);
                        for(int k=list.size()-1;k>=0;k--){
                            if(des<=list.get(k)&&list.get(k)<y){
                                pos=list.get(k)+1;
                                break;
                            }
                        }
                        
                    }
                    y=pos;
                }
                //向西走
                if(dir==3){
                   int des=x-commands[i];
                   int pos=des;
                    if(line.containsKey(y)){
                        List<Integer> list=line.get(y);
                        for(int k=list.size()-1;k>=0;k--){
                            if(des<=list.get(k)&&list.get(k)<x){
                                pos=list.get(k)+1;
                                break;
                            }
                        }
                       
                    }
                     x=pos;
                }
            }
            res=Math.max(res,x*x+y*y);
        }
        return res;
    }
}

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92