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 = 1;
}
vector<string>res;
for(int i = 0; i < store1.size(); i++){
string temp = "";
for(int j = 0; j < store1.size(); j++){
if(store1 == 0){
temp += '_';
}else{
temp += 'X';
}
}
res.push_back(temp);
}
res = cur_direction;
return res;
}
};
{:10_312:}
页:
[1]