C++刷LeetCode（面试题 16.22. 兰顿蚂蚁）【模拟】

糖逗

题目描述：

1. 一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。
   
2. 
   
3. (1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
   
4. (2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
   
5. 
   
6. 编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
   
7. 
   
8. 网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
   
9. 
   
10. 示例 1:
    
11. 
    
12. 输入: 0
    
13. 输出: ["R"]
    
14. 示例 2:
    
15. 
    
16. 输入: 2
    
17. 输出:
    
18. [
    
19.   "_X",
    
20.   "LX"
    
21. ]
    
22. 示例 3:
    
23. 
    
24. 输入: 5
    
25. 输出:
    
26. [
    
27.   "_U",
    
28.   "X_",
    
29.   "XX"
    
30. ]
    
31. 说明：
    
32. 
    
33. K <= 100000
    
34. 
    
35. 来源：力扣（LeetCode）
    
36. 链接：https://leetcode-cn.com/problems/langtons-ant-lcci
    
37. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     vector<string> printKMoves(int K) {
   
4.         //模拟
   
5.         char cur_direction = 'R';
   
6.         pair<int, int>cur_position(0, 0);
   
7.         set<pair<int, int> >black;
   
8.         int row_low = 0, row_high = 0;
   
9.         int col_low = 0, col_high = 0;
   
10.         for(int i = 0; i < K; i++){
    
11.             auto iter = black.find(cur_position);
    
12.             int direction1 = cur_position.first;
    
13.             int direction2 = cur_position.second;
    
14.             if(iter == black.end()){
    
15.                 //在白色格子上
    
16.                 //(1)翻转
    
17.                 black.insert(cur_position);
    
18.                 //(2)改变方向&&前进一步
    
19.                 if(cur_direction == 'R'){
    
20.                     cur_direction = 'D';
    
21.                     cur_position = make_pair(direction1+1, direction2);
    
22.                 }else if(cur_direction == 'L'){
    
23.                     cur_direction = 'U';
    
24.                     cur_position = make_pair(direction1-1, direction2);
    
25.                 }else if(cur_direction == 'U'){
    
26.                     cur_direction = 'R';
    
27.                     cur_position = make_pair(direction1, direction2+1);
    
28.                 }else if(cur_direction == 'D'){
    
29.                     cur_direction = 'L';
    
30.                     cur_position = make_pair(direction1, direction2-1);
    
31.                 }
    
32.             }else{
    
33.                 //在黑格子上
    
34.                 //(1)翻转
    
35.                 black.erase(iter);
    
36.                 //(2)改变方向&&前进一步
    
37.                 if(cur_direction == 'R'){
    
38.                     cur_direction = 'U';
    
39.                     cur_position = make_pair(direction1-1, direction2);
    
40.                 }else if(cur_direction == 'L'){
    
41.                     cur_direction = 'D';
    
42.                     cur_position = make_pair(direction1+1, direction2);
    
43.                 }else if(cur_direction == 'U'){
    
44.                     cur_direction = 'L';
    
45.                     cur_position = make_pair(direction1, direction2-1);
    
46.                 }else if(cur_direction == 'D'){
    
47.                     cur_direction = 'R';
    
48.                     cur_position = make_pair(direction1, direction2+1);
    
49.                 }
    
50.             }
    
51.             row_low = min(row_low, cur_position.first), row_high = max(row_high, cur_position.first);
    
52.             col_low = min(col_low, cur_position.second), col_high = max(col_high, cur_position.second);
    
53.            
    
54.         }
    
55.         int row_len = row_high - row_low + 1;
    
56.         int col_len = col_high - col_low + 1;
    
57.         vector<vector<int> >store1(row_len, vector<int>(col_len, 0));
    
58.         for(auto cha : black){
    
59.             int temp1 = (cha.first - row_low);
    
60.             int temp2 = (cha.second - col_low);
    
61.             store1[temp1][temp2] = 1;
    
62.         }
    
63.         vector<string>res;
    
64.         for(int i = 0; i < store1.size(); i++){
    
65.             string temp = "";
    
66.             for(int j = 0; j < store1[0].size(); j++){
    
67.                 if(store1[i][j] == 0){
    
68.                     temp += '_';
    
69.                 }else{
    
70.                     temp += 'X';
    
71.                 }
    
72.             }
    
73.             res.push_back(temp);
    
74.         }
    
75.         res[cur_position.first- row_low][cur_position.second- col_low] = cur_direction;
    
76.         return res;
    
77.     }
    
78. };
    

复制代码

糖逗