看完电影,突然想到Paris和Helen还在地牢里呆着呢,得在学泛型算法之前救他们出来啊.于是拿起纸和笔坐到马桶上,就开始想了.
回想起那个Helen不动的版本,算法也就是找到了所有的可能性,一步一步的走.那么,既然要找最短路径,我想,找遍所有的可能性是必须的,Helen会动也一样.怎样才能一点都不放过呢?在实践一里面,每走到一点,记录下走到这一点所花的步数,同时做个标记,就不会从别的路来这了.而且,搜寻的时候是广度优先,这样就保证了每到一点所花的步数都是最小的.
但是,Helen如果会动,情况就复杂了.比如可能为了让Helen从某个死胡同里面出来,Paris得重复经过某个点.既然Paris经过某个点可能不只一次,那么,什么是"唯一"的呢??一对点呗!如果某个时刻Paris在A点而Helen在B点,走了n步之后Paris又到了A同时Helen又到了B,那显然这n步是白走了!
好了,那我们搜寻的时候还是广度优先,找这样一对对的点,不就ok了?
冲水,开始动手写吧!
--------------------------
看题目点这里
--------------------------
首先,我们定义FindWay类,学完了C++的容器部分,解决问题果然很有用啊.
先是类的私有成员,我是这样定义的:
typedef pair<int,int> Coordi;
typedef pair<Coordi,Coordi> Dou_coordi;
private:
vector<vector<char> > maze;//存储地牢
int lines;//行数
int columns;//列数
char pton;//paris向北走时,helen的行动方向
char ptos;//paris向南走时,helen的行动方向
char ptow;//paris向西走时,helen的行动方向
char ptoe;//paris向东走时,helen的行动方向
Coordi paris;//Paris的位置
Coordi helen;//Helen的位置
int steps;//当前已走的步数
multimap<int,Dou_coordi> came_points;
//multimap容器,存放paris和helen同时来过的一对对点的集合
根据题目的要求,我们要设定地牢的大小,设置地牢里每一点的标志,放入Paris和Helen,还要设置Helen的行动方向.最后得出需要的步数.因此,我定义了下面几个公共成员函数:
public:
bool set_size(int m,int n,string &help);//检查地牢的大小是否符合要求,设置地牢大小
void set_flag(int x,int y,char flag)//设置地牢里每一点的标志
{
if(flag=='P')
{
paris=make_pair(x,y);
flag='.';
}
else if(flag=='H')
{
helen=make_pair(x,y);
flag='.';
}
maze[x][y]=flag;
}
bool is_effective(string &help) const;//检查地牢是否是封闭的,以及是否放入了Paris和Helen
void set_direction(char tn,char ts,char tw,char te)//存入Helen相应的行动方向
{
pton=tn;
ptos=ts;
ptow=tw;
ptoe=te;
}
int get_steps();//计算并返回步数,如果找不到路则返回-1
set_flag()函数因为要用到很多次,把它定义在头文件中,这样它就是一个内联函数.set_direction()很短,也把他定义在头文件中.另外有些函数中的help参数是为了返回错误信息.
接下来就可以写主函数了:
View Code
#include "stdafx.h"
#include <iostream>
#include <string>
#include "FindWay.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
FindWay fd;
cout<<"请输入两个大于等于3小于等于20的数字,分别表示迷宫的行数和列数,用空格隔开:"<<flush;
int m,n;
string size_help;
cin>>m>>n;
if(!fd.set_size(m,n,size_help))
{
cout<<size_help<<endl;
system("PAUSE");
return -1;
}
cout<<"请输入字符用以描述地图.“.”代表通路，“#”代表岩石，“!”代表熔浆，“H”表示Helen,“P”表示Paris。"<<endl
<<"输入完第一行再输入第二行,以此类推.用空格隔开."<<endl
<<"你需要输入"<<m<<"乘以"<<n<<"等于"<<m*n<<"个字符:"<<endl;
char flag;
string maze_help;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
cin>>flag;
fd.set_flag(i,j,flag);
}
if(!fd.is_effective(maze_help))
{
cout<<maze_help<<endl;
system("PAUSE");
return -1;
}
cout<<"请输入四个字符“n”（北），“s”（南），“w”（西），“e”（东）的排列，"
<<"表示Paris分别向NSWE四个方向走时Helen受磁石磁力影响的移动方向:"<<endl;
char tn,ts,tw,te;
cin>>tn>>ts>>tw>>te;
fd.set_direction(tn,ts,tw,te);
int steps=fd.get_steps();
if(steps<0)
cout<<"可惜,找不到可以遇见Helen的道路!"<<endl;
else
cout<<"走"<<steps<<"步之后可以遇见Helen!"<<endl;
system("PAUSE");
return 0;
}
下面,我们就可以不关心别的,专心实现刚才声明的三个公共成员函数.
其中set_size()和is_effective()这两个函数比较简单:
bool FindWay::set_size(int m,int n,string &help)//检查地牢的大小是否符合要求,设置地牢大小
{
if(m<3||m>20)
{
help="行数应该在3到20之间!";
return false;
}
if(n<3||n>20)
{
help="列数应该在3到20之间!";
return false;
}
lines=m;
columns=n;
paris=make_pair(0,0);
helen=make_pair(0,0);
maze.resize(lines+1,vector<char>(columns+1));
//为了更易读,不使用下标'0',所以容器要定义的大一号
return true;
}
bool FindWay::is_effective(string &help) const
//检查地牢是否是封闭的,以及是否放入了Paris和Helen
{
if(paris.first==0)
{
help="没有在地图上指定Paris的位置!";
return false;
}
else if(helen.first==0)
{
help="没有在地图上指定Helen的位置!";
return false;
}
for(int i=1;i<=lines;i+=(lines-1))
for(int j=1;j<=columns;j++)
if(maze[i][j]=='.'||maze[j][i]=='.')//这样就可以检查地牢的四周
{
help="地牢应该是封闭的,四周应该是岩石或者熔浆!";
return false;
}
return true;
}
到了最重要的get_steps()函数.在定义它之前,先来定义几个私有成员函数,我们经常要判断Paris或Helen能不能向某个方向移动,如果没有被挡住可以还要判断"这一对点"是不是已经来过了.另外我们要判断Paris和Helen是不是已经相遇了.因此,我定义了下面四个私有成员函数:
private:
int meet()//判断Paris和Helen是否相遇
{
return abs(paris.first-helen.first)+abs(paris.second-helen.second);
//0表示已经在同一点;1表示相邻,经过一次移动即可相遇
}
Coordi &move(char dir,Coordi &new_coordi)//得到Paris或Helen移动后的坐标
{
switch (dir)
{
case 'n':
new_coordi.first--;
break;
case 's':
new_coordi.first++;
break;
case 'w':
new_coordi.second--;
break;
case 'e':
new_coordi.second++;
break;
}
return new_coordi;
}
bool alive(char p_dir,Coordi &p_coordi,char h_dir,Coordi &h_coordi);
//Paris和Helen的移动是否会被挡住,可行返回true,并且返回移动后两人的坐标.
void walk(const char pto,const char hto);
//向某个方向移动一步,pto表示Paris的移动方向,hto为Helen的移动方向
其中alive()和walk()的定义如下:
typedef multimap<int,Dou_coordi>::iterator Dcoordi_iter;
bool FindWay::alive(const char p_dir,Coordi &p_coordi,char h_dir,Coordi &h_coordi)
{
p_coordi=move(p_dir,p_coordi);
char p_flag=maze[p_coordi.first][p_coordi.second];
if(p_flag!='.')
return false;//Paris不管遇到石头还是熔浆都走不了
h_coordi=move(h_dir,h_coordi);
char h_flag=maze[h_coordi.first][h_coordi.second];
if(h_flag=='!')
return false;//Helen遇到熔浆就会死
else if(h_flag=='#')
h_coordi=helen;//遇到石头就原地不动
return true;
}
void FindWay::walk(const char pto,const char hto)
{
Coordi new_paris(paris);
Coordi new_helen(helen);
Dou_coordi new_points;
if(alive(pto,new_paris,hto,new_helen))
//如果不会被挡到,就看这一对点是不是已经来过了
{
new_points=make_pair(new_paris,new_helen);
Dcoordi_iter diter=came_points.begin();
while(diter!=came_points.end())
{
if(diter->second==new_points)
break;//已经来过了
diter++;
}
if(diter==came_points.end())
came_points.insert(make_pair(steps+1,new_points));
//没有来过,就把这一对点插入到came_points容器中
}
}
写好这些函数,再写get_steps()就不难了:
int FindWay::get_steps()
{
steps=0;
came_points.insert(make_pair(steps,make_pair(paris,helen)));
//将最开始的一对点插入到容器中
Dcoordi_iter iter=came_points.begin();
while(iter!=came_points.end())
{
pair<Dcoordi_iter,Dcoordi_iter> diter=came_points.equal_range(steps);
//广度优先,从所有步数为steps的"点对(Dou_coordi)"分别出发
while(diter.first!=diter.second)
{
paris=(diter.first->second).first;
helen=(diter.first->second).second;
int me=meet();
if(me<=1)
return steps+me;//遇见!
walk('n',pton);//向北
walk('s',ptos);//向南
walk('w',ptow);//向西
walk('e',ptoe);//向东
diter.second=came_points.upper_bound(steps);
//更新diter.second迭代器,这很重要.
diter.first++;//步数同为steps的下一点
}
iter=diter.second;
steps++;//步数加1
}
return -1;//无法遇见.
}
好吧,事实是,我是先写get_steps()函数,写着写着觉得再写几个私有成员函数就简洁了...
这应该不是最简单的方法,不过感觉类写的还是比较有逻辑性,比较易读的,比Helen不动的那个版本有了进步.
<三傻大闹宝莱坞>是一部难得的佳片,推荐!
附:代码文件(环境是VC++ 2008)
作者: Barryhe 发表于 2011-04-24 15:19 原文链接
评论: 2 查看评论 发表评论
最新新闻：
· 调研称超1/3年轻人视网络如空气：离开无法生存(2011-11-04 14:09)
· 社交旅游网站Gogobot融资1500万美元，打造旅游爱好者的全能助手(2011-11-04 13:54)
· Digg创始人Kevin Rose新项目Oink上线，让你为周围的任何东西打分(2011-11-04 13:53)
· Dark Sky：无温度，无湿度，无风力的天气预报(2011-11-04 13:39)
· “摇一摇，味道更好”——雅虎发布“鸡尾酒”Web开发技术(2011-11-04 13:36)
编辑推荐：你正在成长为一名优秀的程序员吗？
网站导航：博客园首页 我的园子 新闻 闪存 小组 博问 知识库
文章来源:
http://www.cnblogs.com/heqile/archive/2011/04/24/2026195.html