国外同学让帮忙的一个C++机器人程序

Question

一朋友在英国读书，老师安排了一个C++的作业，想让我帮下忙，可是我已经不做C++好久了。所以很多都记不起来了。

感觉这个题目还挺有意思，不知道有没有人能帮忙试一下。下面我发一下需求：

1.作业说明及要求：

 This exercise is motivated by a problem in robotics. The idea is that there is a robot exploring an unknown terrain. The robot starts with a vague information about the surroundings and as it goes along it improves its view of the environment.
The exercise is not meant to be completely realistic! This is just the motivation.

The main concepts that you will be practicing during this assessment are inheritance, virtual functions, and the usage of some of the features of the STL.

A few more details about the setting of the exercise.
The idea is that there is an arena in which a robot is going around. As the robot goes around it learns more about the environment it refines its information regarding where it can and cannot go and what is the cost of going through different areas.

You are asked to implement the classes:

1. Arena - the base class of all the hierarchy.

2. OneCell - an abstract class represnting areas for which not much is known and they are summarized as one area.

3. Cell - an area that is thought to be passable that has a price (in terms, e.g., of energy) that it would cost to pass through.

4. Block - an area that is thought to be not passable.

5. Zone - an area that was refined and contains a greed of areas about which something is known.

The idea would be to start with some zone that has some basic information about the arena (i.e., it contains an array/vector/whatever you want of OneCells). Then, one of these OneCells is refined with more information and becomes a zone with more refined information.
After this process repeats for a while, you get some kind of recursive maze strucure through which the robot can navigate. The most complicated part of this assessment would be to implement checking whether there is a way to cross this maze.

Technically, I have created the header files of all these classes. You have to complete them with additional members, decide where to implement virtual functions, and complete the implementations. You will have to submit ten files: Arena.*pp, OneCell.*pp, Cell.*pp, Block.*pp, and Zone.*pp. Most of the work will be done in Zone. The header files include detailed descriptions of the functions that you are required to implement.

Materials provided:

1. Arena.cpp

2. Arena.hpp

3. OneCell.hpp

4. Cell.hpp

5. Block.hpp

6. Zone.hpp

7. main.cpp

8. Makefile

9. all.zip - Just one zip file containing everything

Graph Search Algorithms

Here are a few details about how to search whether there is a path across a graph from some part to some other part. This is required for the implementation of the member existsPath.

This is a pseudo code of a search algorithm in graphs:
bool DFS(set<location> placesToStartFrom,set<location> placesToReach)
   stack<location> st;
   set<location> visited;
 
   st.push(placesToStartFrom); 
   while (!st.empty) { 
      location current = st.pop() 
 
   if (visited.find(current)) { 
      continue; 
   } 
 
   visited.add(current) 
 
   if (placesToReach.find(current)) { 
      return true; 
   } 
 
   foreach (neighbor of current) { 
      st.add(neighbor) 
   } 
   } 
   return false; 
}

So the algorithm starts with the set of locations that you want to start from and the set of states you want to reach. Then, it has a stack of the locations that need handling and the set of locations that have been visited. As long as the stack is not empty there is some chance to reach the target. The search proceeds by taking one element from the stack. If that element has already been visited, then clearly there is no reason to search from it again. Otherwise, mark that element visited and check if it is part of the target set. If it is not in the target set continue searching by adding its neighbors to the stack.
A simple optimization is to check if a location is visited before adding it to the stack and not adding it at all if it was already visited.

For the purposes of this assignment, the location should be replaced by a combination of a location in the zone along with the entry direction to it. Then, in order to determine whether something is a neighbor of current you have to check that it is possible to go inside the current location from the entry direction to the exit direction.

If you want to read more about this you should look up the algorithms for depth first search or breadth first search. The algorithm implemented above is DFS.

 2.已经提供的几个文件：

1）Arena.hpp

#ifndef ARENA_HPP_
#define ARENA_HPP_

#include <utility>
#include <string>
#include <vector>
#include <list>

class OneCell;


// These are the directions from which
// one can enter/exit a specific area in the arena.
typedef enum
{
    leftD = -3,
    topD = -1,
    bottomD = 1,
    rightD = 3,
    noD = 5
} Direction;

// These are the movement instructions for a robot
// This is required only for the bonus part
typedef enum
{
    goForwardI,
    turnLeftI,
    turnRightI
} Instruction;

// Used for size and for pointing to a specific cell
// in an arena.
typedef std::pair<unsigned int,unsigned int> TwoD;

// A sequence of movement instructions for a robot
// Used only in the bonus part
typedef std::vector<Instruction> Path;

// A pointer to one cell in the arena.
// This is a linked list of pairs of unsigned ints
// Giving a pointer into the recursive structure of the Arena.
typedef std::list<TwoD> Address;

class Arena {
public:
	Arena();
	virtual ~Arena()=0;

	// Inheriting from oneCell?
	virtual bool oneCell() const=0;

	// Return the dimension of this particular arena
	virtual TwoD dimension() const=0;

	// Return the total number of cells in this arena
	// For example, every OneCell has total size 1.
	// Every Zone has the total size that is the sum of
	// total sizes of its components (recursively).
	virtual unsigned int totalSize() const =0;

	// Is it possible to enter this arena from this direction?
	// Essentially, if all the cells on the "direction" border
	// of this arena are blocked then the answer is no
	// Otherwise the answer is yes.
	// Notice that this may mean that you need
	// to check this recursively.
	virtual bool enter(Direction) const=0;

	// Is it possible to exit this arena from this direction?
	// Essentially, if all the cells on the "direction" border
	// of this arena are block then the answer is no.
	// Otherwise the answer is yes.
	// Notice that this may mean that yo need
	// to check this recursively.
	virtual bool exit(Direction) const=0;

	// Is it possible to cross this arena entering from the
	// first direction and exiting the second direction.
	// Notice that going in a specific part of one arena
	// in a certain direction may need to be checked recursively.
	//
	// Notice that the following situation is possible:
	// Zone1 (where X denotes a block):
	// XXX
	//   X
	// X
	// XXX
	// Zone2
	// XXX
	//   X
	// X
	// XXX
	// As in Zone1 you can cross from left to right and in Zone2
	// you can cross from left to right you should say that
	// when putting Zone1 next to Zone2 it is possible to cross from
	// left to right.
	// Even though when putting the two elements together you get:
	// XXXXXX
	//   X  X
	// X  X
	// XXXXXX
	// Which clearly has no path from left to right.
	// So the result of your existsPath should just call the recursive
	// existsPath functions of the respective components and not
	// try to align the entrances and exits of different zones.
	// This would be quite complicated as the different zones could have
	// different sizes.
	virtual bool existsPath(Direction,Direction) const=0;

	// Get a pointer to a location in the Arena.
	// If that location is a Zone return 0
	// If that location does not exist return 0
	// If that location is a OneCell return a pointer to it.
	//
	// The way the address works is that the first position in the
	// list tells you which Area of the current Arena to go into.
	// Then, when you go into that area, the rest of the linked list
	// tells you where you should go further.
	// When you get to the last element of the linked list
	// that element should tell you to choose an area of the current
	// Arena that is a OneCell.
	// If it is not, you should protest.
	// So if the linked list is too long or too short this function
	// should return null.
	//
	// Notice that the linked list is passed by reference.
	// You can change the linked list as you go along it to
	// make your search more efficient.
	virtual OneCell* find(Address&)=0;

	// Get a pointer to a location in the Arena.
	// If that location is not a OneCell (see above) return false.
	// Otherwise, that location should be refined to a zone
	// with the information supplied to the constructor.
	// Notice that the information supplied matches the zone constructor.
	// As in assessment 2 the access to the dimensions of the array
	// are: [width][height].
	// So, if I have an array of size 4x3 the access to
	// array[3][2] should be possible and the access to
	// array[2][3] would lead to an access violation!
	//
	// See the constructor of Zone for further details!
	virtual bool findRefine(Address&,unsigned int,unsigned int,int**)=0;

	// Pretty print of the direction (supplied)
	// Use for debugging purposes
	std::string direction(Direction) const;

	// Printing function for your debugging purposes.
	// Will not be evaluated
	// A stub is provided so that you don't have
	// to implement this.
	virtual std::string toString() const;
private:
	// TODO: implement this
};

#endif /* ARENA_HPP_ */

2)Arena.cpp

#include "Arena.hpp"

Arena::Arena() {}

Arena::~Arena() {}

std::string Arena::direction(Direction d) const {
	switch(d) {
	case (leftD): return "left";
	case (rightD): return "right";
	case (topD): return "top";
	case (bottomD): return "bottom";
	default: return "noD";
	}
}

std::string Arena::toString() const {
	// TODO: implement this.
	return "";
}

3)OneCell.hpp

/*
 * OneCell.hpp
 *
 *  Created on: 8 Dec 2013
 *      Author: np183
 */

#ifndef ONECELL_HPP_
#define ONECELL_HPP_

// class OneCell;

#include "Arena.hpp"

class OneCell: public Arena {
public:
	// TODO: Implement this

	// Every one cell has a value that signifies
	// the "price" of passing it.
	// For a Block, this is -1 signifying infinity
	// For a Cell, this could be every other number
	virtual int value() const=0; // Notice- new virtual function!

	// TODO: Implement this
private:
	// TODO: Implement this
};

#endif /* ONECELL_HPP_ */

4)Block.hpp

#ifndef BLOCK_HPP_
#define BLOCK_HPP_

#include "OneCell.hpp"

class Block: public OneCell {
public:
	// TODO: implement this
private:
	// TODO: implement this
};

#endif /* BLOCK_HPP_ */

5)Cell.hpp

#ifndef CELL_HPP_
#define CELL_HPP_

#include "OneCell.hpp"

class Cell: public OneCell {
public:
	Cell();
	Cell(int);
	virtual ~Cell();

	// TODO: Implement this
private:
	// TODO: Implement this
};

#endif /* CELL_HPP_ */

6)Zone.hpp

#ifndef ZONE_HPP_
#define ZONE_HPP_

#include "Arena.hpp"


class Zone: public Arena {
public:
	// This is a constructor of a Zone from an array.
	// You need to construct a zone of width and height as given.
	// Every entry in the array indicates what kind of OneCell
	// that location in the Zone should have.
	// If the entry in the array is -1 this should be a block.
	// If the entry in the array is positive or 0 this should be
	// a Cell and the number should be its value.
	//
	// Notice that the access to the array is as in assessment 2.
	// That is:
	// If width=3, height=2 then:
	// array[2][1] is accessible and array[1][2] is not.
	// Location (2,1) of the Zone should correspond to
	// array[2][1].
	Zone(unsigned int width, unsigned int height, int** array);
	virtual ~Zone();

	// TODO: Implement this
private:
	// No need to implement
	Zone();

	// TODO: Implement this
};

#endif /* ZONE_HPP_ */

7)main.cpp

#include <string>
#include <iostream>
#include <cstdlib>
#include "Zone.hpp"
#include "Cell.hpp"
#include "Block.hpp"

using std::string;
using std::cerr;
using std::cout;
using std::endl;

int main(int argc, char* argv[]) {
	Cell c;
	Block b;

	const unsigned int SIZE=20;
	int **arr=new int*[SIZE];
	for (unsigned int i=0 ; i< SIZE ; ++i) {
		arr[i]=new int[SIZE];
		for (unsigned int j=0 ; j<SIZE ; ++j) {
			int temp=rand()%3;
			arr[i][j]= (temp ? (rand()%50)-50 : -1);
		}
	}
	Zone z(SIZE,SIZE,arr);

	cout << z.toString() << endl;

	for (int i=-3 ; i<5 ; i+=2) {
		for (int j=-3 ; j<5 ; j+=2) {
			if (i==j)
				continue;
			Direction from=static_cast<Direction>(i);
			Direction to=static_cast<Direction>(j);
			cout << "There is ";
			if (b.existsPath(from,to)) {
				cout << "a ";
			}
			else {
				cout << "no ";
			}
			cout << "path from " << c.direction(from) <<
					" to " << c.direction(to) << endl;

		}
	}
	if (z.existsPath(leftD,topD))
	return 0;
}

Answer 1

呵呵呵呵，咋出去的？丢人啊

Answer 2

(⊙o⊙)…干嘛这么说我啊。。。

Answer 3

好厉害的学校··

Answer 4

！？…～

Answer 5

你是猴子搬来的救兵嘛？

Answer 6

不明觉厉

Answer 7

多少镑?

Answer 8

你同学出价多少!???