alan23273850 的刷題筆記
c082: 00118 - Mutant Flatworld Expolrers
Tags: simulation
出處：https://zerojudge.tw/ShowProblem?problemid=c082
提交：https://zerojudge.tw/Submissions?problemid=c082&account=allllllan123456
問題：給你在二維笛卡兒坐標系底下以原點 (0,0) 為左下角頂點、($m\le50$, $n\le50$) 為右上角頂點之一塊矩形土地，以及上面一些機器人的初始位置及面向方位，每個機器人有各自一連串的移動指令 (不超過 100 個) 需要執行，指令只可能是原地左轉 90 度、原地右轉 90度、依其面向方位向前走一格這三種而已。而且各個機器人是依序動作的，也就是說，直到前一個機器人完成他全部的動作，下一個機器人才會開始動作。另外，因為此矩形土地有邊界，一個機器人一旦走出邊界掉落下去就永遠消失了；只不過機器人有保護後人機制，萬一不幸跑出邊界，在掉落前的區塊會設下一個標記，那麼之後的機器人一旦採在這塊標記上的時候就會忽略會讓他掉下去的指令。舉例來說，有機器人曾經在 (0,0) 往南邊走出邊界，那麼下一個機器人再次到達 (0,0) 的時候就至少不會再往南邊或西邊走 $($當 $m>0$、$n>0)$。請問這些機器人走完各自的指令之後會到達哪裡、面對何方位？如果不幸掉落，掉落前的位置、面對何方位？
解法：方向編碼以及安全標記的設計是重點。詳細可參考程式碼。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 map<char, char> charToNum = {{'N',0}, {'E',1}, {'S',2}, {'W',3}},
6 numToChar = {{0,'N'}, {1,'E'}, {2,'S'}, {3,'W'}};
7 char dir; bool safe[51][51] = {false};
8 int x, y, xMAX, yMAX; cin >> xMAX >> yMAX;
9 while (cin >> x >> y >> dir) { string str; cin >> str;
10 dir = charToNum[dir]; bool lost = false;
11 for (auto ch: str) {
12 if (ch == 'R') dir = (dir+1) % 4;
13 else if (ch == 'L') dir = (dir+3) % 4;
14 else { assert(ch == 'F');
15 int tX = x, tY = y;
16 x += (dir==1) - (dir==3);
17 y += (dir==0) - (dir==2);
18 if (x<0 || x>xMAX || y<0 || y>yMAX) {
19 x = tX; y = tY;
20 if (safe[tX][tY]) continue; // cannot happen again
21 safe[tX][tY] = true;
22 lost = true; break;
23 }
24 }
25 }
26 cout << x << ' ' << y << ' ' << numToChar[dir]
27 << (lost ? " LOST" : "") << '\n';
28 }
29 return 0;
30}