※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: 把兩個unordermap of unorderset
: 換成一個unorderset
: 應該可以比較快吧:(
: 寫這個才發現
: 我連旋轉矩陣跟三角函數
: 都快忘記怎麼算了
: 想自
: int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
: unordered_map<int,unordered_set<int>> x_obs;
: unordered_map<int,unordered_set<int>> y_obs;
: for(auto v : obstacles) {
: x_obs[v[0]].insert(v[1]);
: y_obs[v[1]].insert(v[0]);
: }
: int cur_dir_x = 0;
: int cur_dir_y = 1;
: int cur_x = 0;
: int cur_y = 0;
: int ans = 0;
: for(auto c : commands) {
: if(c == -2) {
: int tmp = cur_dir_x;
: cur_dir_x = -cur_dir_y;
: cur_dir_y = tmp;
: }
: else if(c == -1) {
: int tmp = cur_dir_x;
: cur_dir_x = cur_dir_y;
: cur_dir_y = -tmp;
: }
: else {
: for (int i=0; i<c; i++) {
: cur_x += cur_dir_x;
: cur_y += cur_dir_y;
: if(x_obs[cur_x].find(cur_y)!=x_obs[cur_x].end() ||
: y_obs[cur_y].find(cur_x)!=y_obs[cur_y].end()) {
: cur_x -= cur_dir_x;
: cur_y -= cur_dir_y;
: break;
: }
: }
: ans = max(ans, cur_x*cur_x+cur_y*cur_y);
: }
: }
: return ans;
: }
思路:
就 照著做 我原本以為一步一步慢慢加會爆
看限制條件 command最大值就9 果斷慢慢加
Python Code:
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) ->
int:
x = 0
y = 0
cur_direction = 0
res = 0
direction = [(0,1),(1,0),(0,-1),(-1,0)]
obstacles = set((x,y) for x, y in obstacles)
for c in commands:
if c == -1:
cur_direction = (cur_direction+1) % 4
elif c == -2:
cur_direction = (cur_direction-1) % 4
else:
while c > 0:
nx = x + direction[cur_direction][0]
ny = y + direction[cur_direction][1]
if (nx,ny) in obstacles:
break
x, y = nx, ny
c -= 1
res = max(res, x * x + y * y)
return res