Thoughtworks公司面試題——MARSROVERS問題

說明：

來源于一個很早的帖子，題目如下，有人做過相關(guān)的解答。

我也花了1個多小時寫了一個，不過這第二個輸出和5×5的地圖沖突，實際上第二個Rover會走出這個地圖。

以下是原題

A squad of robotic rovers are to be landed by NASA on a plateau on Mars.

This plateau, which is curiously rectangular, must be navigated by the rovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth.

A rover\s position and location is represented by a combination of x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North.

In order to control a rover, NASA sends a simple string of letters. The possible letters are \L \, \R \ and \M \. \L \ and \R \ makes the rover spin 90 degrees left or right respectively, without moving from its current spot.

\M \ means move forward one grid point, and maintain the same heading.

Assume that the square directly North from (x, y) is (x, y+1).

INpUT:

The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.

The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover \s position, and the second line is a series of instructions telling the rover how to explore the plateau.

The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover \s orientation.

Each rover will be finished sequentially, which means that the second rover won \t start to move until the first one has finished moving.

OUTpUT

The output for each rover should be its final co-ordinates and heading.

INpUT AND OUTpUT

Test Input:

5 5

1 2 N

LMLMLMLMM

3 3 E

MMRMMRMRRM

火星探測器

一小隊機器人探測器將由NASA送上火星高原，探測器將在這個奇特的矩形高原上行駛。

用它們攜帶的照相機將周圍的全景地勢圖發(fā)回到地球。每個探測器的方向和位置將由一個x,y系坐標圖和一個表示地理方向的字母表示出來。為了方便導(dǎo)航，平原將被劃分為網(wǎng)格狀。位置坐標示例：0，0，N，表示探測器在坐標圖的左下角，且面朝北方。為控制探測器，NASA會傳送一串簡單的字母�？赡軅魉偷淖帜笧椋� \L \, \R \和 \M \。 \L \,和 \R \分別表示使探測器向左、向右旋轉(zhuǎn)90度，但不離開他所在地點。 \M 表示向前開進一個網(wǎng)格的距離，且保持方向不變。假設(shè)以廣場（高原）的直北方向為y軸的指向。

輸入：首先輸入的line是坐標圖的右上方，假定左下方頂點的坐標為0，0。剩下的要輸入的是被分布好的探測器的信息。每個探測器需要輸入wo lines。第一條line 提供探測器的位置，第二條是關(guān)于這個探測器怎樣進行高原探測的一系列說明。位置是由兩個整數(shù)和一個區(qū)分方向的字母組成，對應(yīng)了探測器的（x,y）坐標和方向。每個探測器的移動將按序完成，即后一個探測器不能在前一個探測器完成移動之前開始移動。

輸出：每個探測器的輸出應(yīng)該為它行進到的最終位置坐標和方向。輸入和輸出 測試如下：

期待的輸入:

5 5

1 2 N

LMLMLMLMM

3 3 E

MMRMMRMRRM 期待的輸出

1 3 N

5 1 E

以下是我的答案

說明：

Java語言，OO思想，JDK1.4環(huán)境和4個Class：

Lunch用于程序路口和收入輸出 Controller用于解釋和指揮Rover的行為 Area是plateau的環(huán)境 Rover就是探測器了

寫的匆忙，木有注釋，盡可能的發(fā)揮各位的想象力了，另外打算在東南西北的轉(zhuǎn)換上用循環(huán)雙向列表的，但是又偷懶了（用4取余），導(dǎo)致這里會有點難以理解，算是美中不足吧。

歡迎大家交流 :-)

Lunch.java

package mars;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.*;
import java.util.ArrayList;

public class Lunch {
private static Area area;
private static Controller controller = new Controller();
private static int lineNum = 0;
private static ArrayList roverList = new ArrayList();
private static ArrayList commandList = new ArrayList();

public static void main(String[] args) {

BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
while (true) {
try {
String input = stdin.readLine();
if (lineNum == 0) {
String[] initpoistion = input.split(\" \");
area = controller.createArea(Integer.parseInt(initpoistion[0])
, Integer.parseInt(initpoistion[1]));

}
else {
if (lineNum % 2 == 1) {
String[] initpoistion = input.split(\" \");
Rover rover = controller
.createRover(Integer.parseInt(initpoistion[0]),
Integer.parseInt(initpoistion[1])
, initpoistion[2]
, area);
roverList.add(rover);
}
else {
commandList.add(input);
}
}
if (lineNum == 4)break;
lineNum++;
}
catch (IOException ex) {
}
}
for (int i = 0; i < roverList.size(); i++) {
Rover rover = (Rover) roverList.get(i);
String command = (String) commandList.get(i);
for (int j = 0; j < command.length(); j++) {
char c = command.charAt(j);
if (c == Controller.TURN_LEFT) {
controller.turnLeft(rover);
}
else if (c == Controller.TURN_RIGHT) {

controller.turnRight(rover);
}
else if (c == Controller.MOVE_FOWARD) {
controller.moveFoward(rover, area);
}
else {
System.out.println(\"commond error:\" + c);
}
}

controller.report(rover, area);
}

}
}

Controller.java

package mars;

public class Controller {
public static final char TURN_LEFT = \L\;
public static final char TURN_RIGHT = \R\;
public static final char MOVE_FOWARD = \M\;

public Controller() {
}

public static void report(Rover rover, Area area) {

Rover[][] a = area.getArea();
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
if (a[i][j] == rover) {
System.out.println(i + \" \" + j + \" \" + rover.getDirection());
break;
}
}
}
}

public Area createArea(int x, int y) {
return new Area(x, y);
}

public Rover createRover(int x, int y, String direction, Area area) {
Rover rover = new Rover(direction);
Rover[][] a = area.getArea();
a[x][y] = rover;
return rover;
}

public void turnLeft(Rover rover) {
rover.turnLeft();
}

public void turnRight(Rover rover) {
rover.turnRight();
}

public void moveFoward(Rover rover, Area area) {
boolean needBreak = false;
Rover[][] a = area.getArea();
int x;
int y;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
if (a[i][j] == rover) {
needBreak = true;
x = i;
y = j;
a[x][y] = null;
String direction = rover.getDirection();
//System.out.println(\"X:\" + x + \" Y:\" + y+ \" direction:\"+direction);
if (direction.equals(Rover.EAST_DIR)) {
a[x + 1][y] = rover;
}
else if (direction.equals(Rover.SOUTH_DIR)) {
a[x][y - 1] = rover;
}
else if (direction.equals(Rover.WEST_DIR)) {
a[x - 1][y] = rover;
}
else if (direction.equals(Rover.NORTH_DIR)) {
a[x][y + 1] = rover;
}
else {
System.out.println(\"error direction:\" + direction);
}
if (needBreak)break;
}
if (needBreak)break;
}
}
}

}

Area.java

package mars;

public class Area {

Rover[][] area;

public Area(int x, int y) {
area = new Rover[x][y];
}

public Rover[][] getArea() {
return area;
}
}

Rover.java

package mars;

public class Rover {

public static final String NORTH_DIR = \"N\";
public static final String SOUTH_DIR = \"S\";
public static final String EAST_DIR = \"E\";
public static final String WEST_DIR = \"W\";
private static final String[] DIR = {
EAST_DIR, SOUTH_DIR, WEST_DIR, NORTH_DIR};
private String direction;

public Rover(String direction) {
this.direction = direction;
}

public void turnRight() {
for (int i = 0; i < DIR.length; i++) {
if (direction.equals(DIR[i])) {
int tmep = i + 1;
direction = DIR[tmep % 4];
break;
}
}
}

public void turnLeft() {
for (int i = 0; i < DIR.length; i++) {
if (direction.equals(DIR[i])) {
int tmep = i - 1;
direction = DIR[ (tmep + 4) % 4];
break;
}
}
}

public String getDirection() {
return direction;
}

}

【Thoughtworks公司面試題——MARSROVERS問題】相關(guān)文章：

公司制度建設(shè)方面存在的問題及整改措施12-24

租船問題 租船問題優(yōu)秀教案04-02

面試經(jīng)典問題11-11

《解決問題的策略——從問題想起》教學反思04-06

工程問題教案04-03

面試的經(jīng)典問題及答案03-16

面試經(jīng)典問題及答案06-20

《組合問題》教案03-12

烙餅問題教案03-06

植樹問題說課稿02-26