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

糖逗

题目描述：

一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。

(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。

编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。

网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。

示例 1:

输入: 0
输出: ["R"]
示例 2:

输入: 2
输出:
[
  "_X",
  "LX"
]
示例 3:

输入: 5
输出:
[
  "_U",
  "X_",
  "XX"
]
说明：

K <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/langtons-ant-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<string> printKMoves(int K) {
        //模拟
        char cur_direction = 'R';
        pair<int, int>cur_position(0, 0);
        set<pair<int, int> >black;
        int row_low = 0, row_high = 0;
        int col_low = 0, col_high = 0;
        for(int i = 0; i < K; i++){
            auto iter = black.find(cur_position);
            int direction1 = cur_position.first;
            int direction2 = cur_position.second;
            if(iter == black.end()){
                //在白色格子上
                //(1)翻转
                black.insert(cur_position);
                //(2)改变方向&&前进一步
                if(cur_direction == 'R'){
                    cur_direction = 'D';
                    cur_position = make_pair(direction1+1, direction2); 
                }else if(cur_direction == 'L'){
                    cur_direction = 'U';
                    cur_position = make_pair(direction1-1, direction2);
                }else if(cur_direction == 'U'){
                    cur_direction = 'R';
                    cur_position = make_pair(direction1, direction2+1);
                }else if(cur_direction == 'D'){
                    cur_direction = 'L';
                    cur_position = make_pair(direction1, direction2-1);
                }
            }else{
                //在黑格子上
                //(1)翻转
                black.erase(iter);
                //(2)改变方向&&前进一步
                if(cur_direction == 'R'){
                    cur_direction = 'U';
                    cur_position = make_pair(direction1-1, direction2);
                }else if(cur_direction == 'L'){
                    cur_direction = 'D';
                    cur_position = make_pair(direction1+1, direction2); 
                }else if(cur_direction == 'U'){
                    cur_direction = 'L';
                    cur_position = make_pair(direction1, direction2-1);
                }else if(cur_direction == 'D'){
                    cur_direction = 'R';
                    cur_position = make_pair(direction1, direction2+1);
                }
            }
            row_low = min(row_low, cur_position.first), row_high = max(row_high, cur_position.first);
            col_low = min(col_low, cur_position.second), col_high = max(col_high, cur_position.second);
           
        }
        int row_len = row_high - row_low + 1;
        int col_len = col_high - col_low + 1;
        vector<vector<int> >store1(row_len, vector<int>(col_len, 0));
        for(auto cha : black){
            int temp1 = (cha.first - row_low);
            int temp2 = (cha.second - col_low);
            store1[temp1][temp2] = 1;
        }
        vector<string>res;
        for(int i = 0; i < store1.size(); i++){
            string temp = "";
            for(int j = 0; j < store1[0].size(); j++){
                if(store1[i][j] == 0){
                    temp += '_';
                }else{
                    temp += 'X';
                }
            }
            res.push_back(temp);
        }
        res[cur_position.first- row_low][cur_position.second- col_low] = cur_direction;
        return res;
    }
};

糖逗