亚麻社招oa

[quote]hxuanyu 发表于 2018-8-20 20:22

1. class maze {
   
2. public:
   
3.     int minPathSum(vector& grid, int x, int y) {
   
4. [/quote]
6. 哈哈，才看到真题，原来target不一定在右下角，这样可以4个方向查找，重新写了一遍，lz能帮我看看吗 谢啦
   
7. 
   
8. [code]
   
9. class maze {
   
10. public:
    
11.     int minPathSum(vector<vector<int>>& grid) {
    
12.         if (grid[0][0] == 0) return -1;
    
13. 
    
14.         vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
    
15. 
    
16.         queue<pair<int, int>> que;
    
17.         que.push(make_pair(0, 0));
    
18.         visited[0][0] = true;
    
19. 
    
20.         vector<vector<int>> dirs = { {-1, 0}, {0, 1}, {1,0},{0, -1} };
    
21. 
    
22.         int dis = 1;
    
23.         while (!que.empty()) {
    
24.             int size = que.size();
    
25.             for (int i = 0; i < size; i++) {
    
26.                 auto top = que.front();
    
27.                 que.pop();
    
28.                
    
29.                 if (grid[top.first][top.second] == 9) return dis;
    
30. 
    
31.                 for (auto dir : dirs) {
    
32.                     int newx = top.first + dir[0];
    
33.                     int newy = top.second + dir[1];
    
34. 
    
35.                     if ((newx < 0) || (newy < 0) || (newx >= grid.size()) || (newy >= grid[0].size()) || (grid[newx][newy] == 0)) continue;
    
36. 
    
37.                     que.push(make_pair(newx, newy));
    
38.                     visited[newx][newy] = true;
    
39.                 }
    
40.             }
    
41.             dis++;
    
42.         }
    
43. 
    
44.         return -1;
    
45.     }
    
46. };

复制代码

感谢楼主

这个妹子撞到墙之前只能朝一个方向走还是可以随意变换方向？

shannyhe 发表于 2018-8-20 11:12
补充一下：
卡车找最短距离：
大意是说Amazon 开了新的warehouse，要用卡车给其他地方送货

是找距离0, 0最近的M个么？

lajalex 发表于 2018-8-24 07:32
是找距离0, 0最近的M个么？

对的 是找距离0, 0最近的M

earlybirds 发表于 2018-8-24 05:50
这个妹子撞到墙之前只能朝一个方向走还是可以随意变换方向？

4个方向 就是b f s 4个方向遍历

shannyhe 发表于 2018-8-24 08:31
4个方向 就是b f s 4个方向遍历

感觉好难　怎么储存最短步数呢

earlybirds 发表于 2018-8-24 23:26
感觉好难　怎么储存最短步数呢

啊 level order traverse 按层数遍历吖 碰到目的地就是最短的啦

LZ请问你做完后问你分析时间复杂度的时候还问了空间复杂度吗

人可木卯 发表于 2018-8-29 14:58
LZ请问你做完后问你分析时间复杂度的时候还问了空间复杂度吗

系统问了