2011ACM大赛题目之贪吃蛇算法

一条贪吃的蛇在一个n*m的网格中游走，它只能从一个方格走向另一个相邻的方格，这里相邻的意思是两个方格有公共边。每个方格可以看作是一个房间，其中一些是空的，一些存放有苹果。贪吃的蛇根本不进入空的房间，而进入有苹果的房间后就可以带走所有苹果使房间成为空的。蛇从一个指定的房间出发，最终回到它的家，把一路带来的苹果存储到家中，当然，它希望带来的苹果最多。请编写程序，输入有整数n和m，及n*m的一个矩阵，矩阵元素数值中有一个是 -1，表示蛇的出发位置，有一个是 -2，表示蛇的家的位置，其余数值是非负整数，0表示房间为空，非零整数表示苹果的数目。输出蛇选择的游走路径和获得的最多的苹果数目。

例如输入4*4矩阵：
7 0 4 18
4 0 1 1
15 7 11 -1
0 12 -2 0

则应输出 (2, 3), (1, 3), (0, 3), (0, 2), (1, 2), (2, 2), (2, 1), (3, 1), (3, 2), 带回苹果数为1+18+4+1+11+7+12 = 54。

（本题为2011年ACM大赛题目）。（可查阅：吕国英，任瑞征等编著，算法设计与分析（第2版），清华大学出版社，2009年1月，第200-202页。

提示：这是一个利用回溯算法的迷宫搜索类型问题，可参考类似问题的已有解法。

哈哈，连夜把算法写出来了，跟各位码友分享一下：

// GreedySnake.cpp 

#include "stdafx.h"
#include <iostream>
#include <Windows.h>
#include <vector>

using namespace std;

#define M 4
#define N 4

//定义数组元素结构体
struct stElement
{
	int i;
	int j;
	int value;
};

int apple[M][N] = { 7,  -1,  4,  18,
	4,  0,  1,   1,
	15,  7, 11,  100,
	0, 12, -2,   0};

vector<stElement> maxPath;//当前最长路径(路径长度指的是路径上所有苹果的总个数）
int maxLen = 0;//最长路径长度

void Snake(vector<stElement> path, int pathLen, int i, int j)
{
	if (apple[i][j] == -2) //如果吃到终点的苹果
	{
		if (pathLen > maxLen) //求最大路径长度
		{
			stElement e;
			e.i = i;
			e.j = j;
			e.value = apple[i][j];
			path.push_back(e);
			maxPath = path;
			maxLen = pathLen;
		}
		return;
	}
	else
	{
		if (i >= 0 && i < M && j >= 0 && j < N && apple[i][j] != 0 )
		{
			stElement e;
			e.i = i;
			e.j = j;
			e.value = apple[i][j];
			path.push_back(e);
			if (apple[i][j] != -1)
				pathLen += apple[i][j];
			int t = apple[i][j];
			apple[i][j] = 0;  //将吃掉的苹果置为0，以免重复搜索

			Snake(path, pathLen, i+1, j);
			Snake(path, pathLen, i-1, j);
			Snake(path, pathLen, i, j-1);
			Snake(path, pathLen, i, j+1);

			apple[i][j] = t;  //4个方向都搜索完之后一定要将元素恢复原状
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{

	vector<stElement> path;
	int i,j,pathLen = 0;
	stElement e;

	//找到入口点
	for (i = 0; i < M; i++)
		for (j = 0; j < N; j++)
		{
			if (apple[i][j] == -1)
			{
				e.i = i;
				e.j = j;
				e.value = -1;
				break;
			}
		}

	Snake(path, pathLen, e.i, e.j);

	cout<<"the longest path:"<<endl;
	for (i = 0; i < maxPath.size(); i++)
		cout<<"("<<maxPath[i].i<<", "<<maxPath[i].j<<")"<<"\t";
	cout<<endl;
	cout<<"带回苹果数为:   "<<maxLen<<endl;
	system("pause");
	return 0;
}