首页 > 基础算法 > 模拟法 > hdu 1620 Mutant Flatworld Explorers-计算几何-[解题报告]
2013
12-16

hdu 1620 Mutant Flatworld Explorers-计算几何-[解题报告]

Mutant Flatworld Explorers

问题描述 :

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

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 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

输出:

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.

样例输入:

5 3
1 1 E
RFRFRFRF
3 2 N
FRRFLLFFRRFLL
0 3 W
LLFFFLFLFL

样例输出:

1 1 E
3 3 N LOST
2 3 S

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct POINT {int x; int y;};
int main(void) {
	//vecScent用于记录之前损失的机器人留下的信息
	vector<int> vecScent;
	//szIns为指令集,szOri为方向转换表
	char szIns[100], szOri[4] = {'N', 'E', 'S', 'W'};
	//ptSize记录地图尺寸,ptPos记录当前位置,ptOri为对应的方向偏移量
	POINT ptSize, ptPos, ptOri[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
	//输入地图尺寸
	cin >> ptSize.x >> ptSize.y;
	//循环处理输入的每一个机器人
	for (char cOri; cin >> ptPos.x >> ptPos.y >> cOri >> szIns; ) {
		//确定初始方向对应的编号
		int nOri = find(&szOri[0], &szOri[4], cOri) - &szOri[0], i = 0;
		//循环处理每一步移动
		for (; szIns[i] != 0; ++i) {
			//向左转或向右转
			if (szIns[i] != 'F') {
				nOri = (nOri + (szIns[i] == 'L' ? 3 : 1)) % 4;
				continue;
			}
			//向前移动,计算出将要移动到的坐标
			POINT ptNew = {ptPos.x + ptOri[nOri].x, ptPos.y + ptOri[nOri].y};
			//如果本次移动未造成损失,则保存新坐标
			if (ptNew.x >= 0 && ptNew.x <= ptSize.x &&
				ptNew.y >= 0 && ptNew.y <= ptSize.y) {
					ptPos = ptNew;
					continue;
			}
			//否则,按损失前的位置和方向进行损失编码
			int nScent = ptPos.y * 51 + ptPos.x;// + nOri * 51 * 51;
			//在历史记录中查找是否有机器人在此损失
			vector<int>::iterator iEnd = vecScent.end();
			//如果在此尚未有过损失,则损失当前机器人
			if (find(vecScent.begin(), iEnd, nScent) == iEnd) {
				//记录损失信息
				vecScent.push_back(nScent);
				break;
			}
		}
		//按要求输出结果
		cout << ptPos.x << ' ' << ptPos.y << ' ' << szOri[nOri];
		cout << ((szIns[i] == 0) ? "" : " LOST") << endl;
	}
	return 0;
}

解题转自:http://www.cnblogs.com/devymex/archive/2010/08/13/1799316.html