当前位置:   article > 正文

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

睡觉睡觉睡觉睡觉睡觉睡觉睡觉睡觉睡觉睡觉睡觉

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/750246
推荐阅读
相关标签
  

闽ICP备14008679号