Background
Robotics, robot motion planning, and machine learning are areas that
cross the boundaries of many of the subdisciplines that comprise
Computer Science: artificial intelligence, algorithms and complexity,
electrical and mechanical engineering to name a few. In addition,
robots as ``turtles'' (inspired by work by Papert, Abelson,
and diSessa) and as ``beeper-pickers'' (inspired by work by Pattis) have
been studied and used by students as an introduction to programming for
many years.
This problem involves determining the position of a robot exploring a
pre-Columbian flat world.
The Problem
Given the dimensions of a rectangular grid and a sequence of robot
positions and instructions, you are to write a program that determines
for each sequence of robot positions and instructions the final position
of the robot.
A robot
position consists of a grid coordinate (a pair of
integers: x-coordinate followed by y-coordinate) and an orientation
(N,S,E,W for north, south, east, and west). A robot
instruction
is a string of the letters '
L', '
R', and '
F' which
represent, respectively, the instructions:
- Left: the robot turns left 90 degrees and remains on the
current grid point.
- Right: the robot turns right 90 degrees and remains on the
current grid point.
- Forward: the robot moves forward one grid point in the
direction of the current orientation and mantains the same orientation.
The direction
North corresponds to the direction from grid point
(
x,
y) to grid point (
x,
y+1).
Since the grid is rectangular and bounded, a robot that moves ``off'' an
edge of the grid is lost forever. However, lost robots leave a robot
``scent'' that prohibits future robots from dropping off the world at
the same grid point. The scent is left at the last grid position the
robot occupied before disappearing over the edge. An instruction to
move ``off'' the world from a grid point from which a robot has been
previously lost is simply ignored by the current robot.
The Input
The first line of input is the upper-right coordinates of the rectangular
world, the lower-left coordinates are assumed to be 0,0.
The remaining input consists of a sequence of robot positions and
instructions (two lines per robot). A position consists of two integers
specifying the initial coordinates of the robot and an orientation
(N,S,E,W), all separated by white space on one line. A robot
instruction is a string of the letters 'L', 'R', and 'F' on one line.
Each robot is processed sequentially, i.e., finishes executing the robot
instructions before the next robot begins execution.
Input is terminated by end-of-file.
You may assume that all initial robot positions are within the bounds of
the specified grid. The maximum value for any coordinate is 50. All
instruction strings will be less than 100 characters in length.
The Output
For each robot position/instruction in the input, the output should
indicate the final grid position and orientation of the robot. If a
robot falls off the edge of the grid the word ``LOST'' should be printed
after the position and orientation.
Sample Input
5 3
1 1 E
RFRFRFRF
3 2 N
FRRFLLFFRRFLL
0 3 W
LLFFFLFLFL
Sample Output
1 1 E
3 3 N LOST
2 3 S
出處:
UVa Online Judge - Mutant Flatworld Explorers
問題敘述
此問題會先輸入兩個整數，表示這個矩形右上角的座標，接著會輸入多組測試資料，每組測試資料兩行，一直到輸入結束為止。每組測試資料第一行輸入的是兩個整數及一個字元，兩個整數代表機器人所在的初始的座標，字元表示面對的方位(E=東, W=西, S=南, N=北)，第二行輸入的則是一行字串代表著一連串的指令(L=左轉, R=右轉, F=往現在面對的方位走一格)。每組輸入會對應一組輸出，此問題要求您輸出經過一連串的指令後，機器人最後所在的座標以及面對的方位為何。若機器人在執行指令的過程中跑出了此矩形的範圍，就輸出它在跑出去前的座標和方位並且印出 LOST，若機器人下次執行指令時，再次在之前跑出去過的座標往矩形外面跑，則此指令視為無效，將會被忽略。
解題思路
這是一個模擬類型的題目，沒有什麼特別的思路，但是要善用資料結構。比如說要如何知道左轉或右轉會轉到哪個方位呢? 我的作法是用一個陣列存{'E', 'N', 'W', 'S'}，然後用一個 index 表示現在所在的位置，index + 1 就是左轉，index - 1 就是右轉，但是注意 index 做加減的時候可能會超出陣列範圍，所以要做環狀處理(意即 index 等於陣列的長度的時候要讓 index = 0，index 小於 0 的時候要讓 index = 陣列的長度 - 1)。其他的就把程式碼交給讀者們參考了。
c++ 程式碼
#include <iostream>
#include <map>
#include <vector>
using namespace std;
bool checkIsLost(int x, int y, int maxX, int maxY) {
return x < 0 || x > maxX || y < 0 || y > maxY;
}
int main() {
int maxX, maxY, x, y;
char ori;
string ins;
char oriArr[4] = {'E', 'N', 'W', 'S'};
int oriArrLen = 4;
map<char, int> oriIndexMap;
oriIndexMap['E'] = 0;
oriIndexMap['N'] = 1;
oriIndexMap['W'] = 2;
oriIndexMap['S'] = 3;
cin >> maxX >> maxY;
vector< vector<bool> > lostTable(maxX + 1, vector<bool>(maxY + 1, false));
while (cin >> x >> y >> ori >> ins) {
int oriIndex;
bool lost = false;
oriIndex = oriIndexMap[ori];
for (int i=0; i<ins.length(); i++) {
switch (ins[i]) {
case 'L':
oriIndex = (oriIndex + 1) % oriArrLen;
break;
case 'R':
if (oriIndex)
oriIndex--;
else
oriIndex = oriArrLen - 1;
break;
case 'F':
switch (oriIndex) {
case 0:
lost = checkIsLost(x + 1, y, maxX, maxY);
if (!lost)
x++;
break;
case 1:
lost = checkIsLost(x, y + 1, maxX, maxY);
if (!lost)
y++;
break;
case 2:
lost = checkIsLost(x - 1, y, maxX, maxY);
if (!lost)
x--;
break;
case 3:
lost = checkIsLost(x, y - 1, maxX, maxY);
if (!lost)
y--;
}
}
if (lost && !lostTable[x][y]) {
lostTable[x][y] = true;
break;
}
}
cout << x << " " << y << " " << oriArr[oriIndex];
if (lost)
cout << " " << "LOST\n";
else
cout << endl;
}
return 0;
}
