ifstream in(\int x,y, k, value; in >> x >> y ;
Grid * grid = new Grid(y, x);
value = 0;
//this block initializes the grid items with ifstream. while (true) {
if (in.eof()) {
break; }
in >> k;
grid->item(value%grid->m_width, value/grid->m_width) = k; value++; }
grid->displayGrid(); grid->run();//done grid->print(); cin >>x;
delete grid; grid = NULL; in.close(); return 0; }
// Snake.cpp : 定义控制台应用程序的入口点。
//This program is used to collect the most mark and output the routine. //by nwpu043814 //date:20100509 #include \#include
using namespace std;
//this struct represents an location. typedef struct {
int x; int y; } Pair;
class Grid {
private :
Grid(const Grid& g); public:
Pair * m_data;
const int m_width; //grid width const int m_height; //grid height int * m_adjacent; //memory array
//constructor with width and height of the grid. Grid(int x, int y):m_width(x), m_height(y) {
m_data = new Pair[x*y];
memset(m_data, 0, x*y *sizeof(Pair)); m_adjacent = new int[x*y];
memset(m_adjacent, -1, x*y *sizeof(int)); }
//free resource ~Grid() {
delete [] m_data;
delete [] m_adjacent; }
int Bin2One(int x, int y) {
return y*m_width + x; }
Pair One2Bin(int index) {
Pair p;
p.x = index % m_width; p.y = index / m_width; return p; }
//this method is used to get or set the item of the grid. int & item(int x, int y) {
return m_data[x+ y*m_width].x; }
//dynamic program main method, it recursively select the next location from the adjacents according to the priority. int getCap(const Pair & loc) {
//this array is used to storage the priority of four adjacents. int value[4] = {0};
//this array is used to access four adjacents according to current location.
int mask[4][2] = {
{-1,0},{0,1},{1,0},{0,-1}/*{x_coordinate, y_coordinate}*/ };
//now, we start to deal with four adjacents. for (int i = 0; i < 4; i++) {
//make sure current location has four adjacents
if (loc.x + mask[i][0] >= 0 && loc.x + mask[i][0] < m_width && loc.y + mask[i][1] >= 0 && loc.y + mask[i][1] < m_height) {
//if the toy in the adjacent can hold current one. int current_toy = (m_data[Bin2One(loc.x, loc.y)].x >
0)?m_data[Bin2One(loc.x, loc.y)].x:m_data[Bin2One(loc.x, loc.y)].y; if ( item(loc.x + mask[i][0], loc.y + mask[i][1]) > current_toy//item(loc.x , loc.y)
|| item(loc.x + mask[i][0], loc.y + mask[i][1]) == 0)//when the adjacent has no toy. {
Pair adjacent;
adjacent.x = loc.x + mask[i][0]; adjacent.y = loc.y + mask[i][1];
m_data[Bin2One(adjacent.x, adjacent.y)].y = current_toy; value[i] = getCap(adjacent); } } }
int sum = 0;
for (int i = 0; i < 4; i++) {
sum += value[i]; }
//when all adjacents is less than current. if (sum == 0) {
return item(loc.x , loc.y); } else {
int index = 0;
int current_max = value[index]; int select = 0;
for (int index = 0; index < 4; index++) {
if (current_max < value[index]) {
current_max = value[index]; select = index; } }
m_adjacent[Bin2One(loc.x, loc.y)] = Bin2One(loc.x + mask[select][0], loc.y + mask[select][1]);
return current_max + item(loc.x , loc.y); } }
//this method drives the class void run() {
Pair loc;
loc.x = 0; loc.y = 0;
for (int i = 0; i < m_width*m_height; i++) {
m_data[i].y = m_data[i].x; }
cout << \}
//display the grid void displayGrid() {
for (int i =0 ; i < this->m_height; i++) {
for (int j = 0; j < this->m_width; j++) {
cout << \ }
cout << endl; } }
//display the routine. void print() {
int current, next, out ; current = 0;
next = m_adjacent[current]; out = m_data[current].x;
while (next != -1) {
cout << \ current = next;
next = m_adjacent[current]; out = m_data[current].x; }
cout << \} };