文档章节

把华为公司面试样题过了一下,用的是宽搜,应该用的是最差的方法,求好方法的指导。

侯禹
 侯禹
发布于 2013/09/08 00:05
字数 940
阅读 78
收藏 0

 

样题-高级题:地铁换乘
已知2条地铁线路,其中A为环线,B为东西向线路,线路都是双向的。经过的站点名分别如下,两条线交叉的换乘点用T1T2表示。编写程序,任意输入两个站点名称,输出乘坐地铁最少需要经过的车站数量(含输入的起点和终点,换乘站点只计算一次)。
地铁线A(环线)经过车站:A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18
地铁线B(直线)经过车站:B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10 T2 B11 B12 B13 B14 B15

据本人目测,是宽搜。先把所有的都链接起来,然后再BFS爆搜一下。

#include<cstdio>
#include <iostream>
#include <queue>
using namespace std;
struct node //规定了每一个车站节点都有上下左右可以走
{
 struct node * up;
 struct node * down;
 struct node * left;
 struct node * right;
 int set;
 char value[5];
 node(){up=NULL;down=NULL;left=NULL;right=NULL;set=0;}
};
struct nodelist//记录一条火车线
{
 node* head;
 node* tail;
 int len;
};
nodelist * lista = new nodelist();//a车站线
nodelist * listb = new nodelist();//b车站线
node *cur1 = new node();
node *cur2 = new node();
queue <node*> que;
node * convert(node * cur,int i)//规定了车的上下左右的移动
{
 switch(i)
 {
 case 0:return cur->up;
 case 1:return cur->down;
 case 2:return cur->left;
 case 3:return cur->right;
 }
}
int BFS(node * startp,node * endp)
{
 que.push(startp);startp->set=1;
 while(!que.empty())
 {
  node *cur = que.front();
  que.pop();
  if(cur == endp)return cur->set;
  for(int i=0;i<4;i++)
  {
   node *afr = convert(cur,i);
   if(afr!=NULL&&afr->set==0)
   {
    afr->set = cur->set + 1;
    que.push(afr);
   }
  }
 }return -1;
}
void init()
{
 int i=0;
 node * p = new node();
 lista->head = p;
 p->value[0] = 'A',p->value[1] = '1'+i;p->value[2] = 0;
 for(i=2;i<=9;i++)
 {
  node * pp = new node ();
  pp->value[0] = 'A',pp->value[1] = '0'+i;pp->value[2] = 0;
  p->right = pp;pp->left = p;p=p->right;
 }
 cur1->value[0]='T',cur1->value[1]='1';cur1->value[2] = 0;
 p->right = cur1;cur1->left = p;p=p->right;
 for(i=10;i<=13;i++)
 {
  node * pp = new node ();
  pp->value[0] = 'A',pp->value[1] = '1',pp->value[2] = '0'+i%10;pp->value[3] = 0;
  p->right = pp;pp->left = p;p=p->right;
 }
 cur2->value[0]='T',cur2->value[1]='2';cur2->value[2] = 0;
 p->right = cur2;cur2->left = p;p=p->right;
 for(i=14;i<=18;i++)
 {
  node * pp = new node ();
  pp->value[0] = 'A',pp->value[1] = '1',pp->value[2] = '0'+i%10;pp->value[3] = 0;
  p->right = pp;pp->left = p;p=p->right;
 }
 p->right = lista->head;lista->head->left = p;
 /*
 node * t = lista->head;
 for(i=0;i<30;i++)
 {
  cout<<"value:"<<t->value<<endl;
  t=t->left;
 }*/
}
void init2()
{
 int i=0;
 node * p = new node();
 listb->head = p;
 p->value[0] = 'B',p->value[1] = '1'+i;p->value[2] = 0;
 for(i=2;i<=5;i++)
 {
  node * pp = new node ();
  pp->value[0] = 'B',pp->value[1] = '0'+i;pp->value[2] = 0;
  p->down = pp;
  pp->up = p;
  p=p->down;
 }
 p->down = cur1;cur1->up = p;p=p->down;
 for(i=6;i<=9;i++)
 {
  node * pp = new node ();
  pp->value[0] = 'B',pp->value[1] = '0'+i;pp->value[2] = 0;
  p->down = pp;pp->up = p;p=p->down;
 }
 
 node * cur3 = new node ();
 cur3->value[0] = 'B',cur3->value[1] = '1',cur3->value[2] = '0';cur3->value[3] = 0;
 p->down = cur3;cur3->up = p;p=p->down;
 p->down = cur2;cur2->up = p;p=p->down;
 for(i=11;i<=15;i++)
 {
  node * pp = new node ();
  pp->value[0] = 'B',pp->value[1] = '1',pp->value[2] = '0'+i%10;pp->value[3] = 0;
  p->down = pp;pp->up = p;p=p->down;
 }
 //node * t = listb->head;
 
 /*for(i=0;i<15;i++)
 {
  cout<<"value:"<<t->value<<endl;
  t=t->down;
 }*/
 
}
 

int main()
{
 init();
 init2();
 freopen("in.txt","r",stdin);
 char start[5],end[5];
 cin>>start>>end;
 int i = 0;
 node * startp;
 node * endp;
 node * cura = lista->head;
 node * curb = listb->head;
 //cin>>start>>end;
 for(i=0;i<21;i++)
 {
  if(strcmp(start,cura->value)==0)
  {
   startp=cura;
   break;
  }
  if(strcmp(start,curb->value)==0)
  {
   startp=curb;
   break;
  }
  if(cura->right!=NULL)cura=cura->right;
  if(curb->down!=NULL)curb=curb->down;
 }

 curb = listb->head;
 for(i=0;i<21;i++)
 {
  //cout<<"cura:"<<cura->value<<"curb:"<<curb->value<<endl;
  if(strcmp(end,cura->value)==0)
  {
   endp=cura;
   break;
  }
  if(strcmp(end,curb->value)==0)
  {
   endp=curb;
   break;
  }
  if(cura->right!=NULL)cura=cura->right;
  if(curb->down!=NULL)curb=curb->down;
 }
 
 int res = BFS(startp,endp);cout<<res-1<<endl;
 return 0;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 96
博文 49
码字总数 34362
作品 0
海淀
程序员
私信 提问
2017暑期实习算法工程师(机器学习)面试经验

面试经验: 腾讯基础研究实习生面试: 首先让自我介绍,简单介绍了科研方向及成果,做过什么项目以及具备那些技能,然后问了我科研是做什么的,我说做移动机器人视觉伺服研究,他可能没懂,我...

m0_37582096
2017/06/01
0
0
七种CSS方式让一个容器水平垂直居中

阅读目录 方法一:position加margin 方法二: diaplay:table-cell 方法三:position加 transform 方法四:flex;align-items: center;justify-content: center 方法五:display:flex;margin:a......

山哥
2016/09/18
46
0
七种css方式让一个容器水平垂直居中

方法一:position加margin 方法二: diaplay:table-cell 方法三:position加 transform 方法四:flex;align-items: center;justify-content: center 方法五:display:flex;margin:auto 方法六......

鼎六智能
2016/10/17
28
0
最近炒得火热的面试要不要笔试的问题,发表点个人观点。

首先个人认为,技术的类的面试 笔试是非必要的,当然如果这个面试官本身是个渣,或者根本不懂一点技术,那么也不排斥笔试一下,但是笔试内容也需要有个具体场景啊; 我是不建议笔试,面试就是...

冰点123
2015/10/19
3.6K
31
江浙沪的java春招实习综合面经

最近也是每天刷牛客看了很多大家的帖子,自己结束春招,把之前的记录分享给大家把。 投递公司 搜狐焦点 爱奇艺散招,快手,金陵科技, 地平线, 有赞,YuxiSoft,搜狐,科大讯飞,腾讯微信,趋...

牛客网
05/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

spring学习笔记(二)spring 事件的使用

spring 中的事件 spring事件通过订阅发布 可以解耦操作 可以同步 可以异步 步骤 编写事件 通过继承org.springframework.context.ApplicationEvent 来编写事件 public ApplicationEvent(Obj...

NotFound403
昨天
13
0
特斯拉车主成功破解了自己Model 3汽车

据汽车博客Electrek消息,一位特斯拉车主成功破解了自己Model 3汽车,还在此基础上运行了Ubuntu。 这位叫trsohmers的网友表示,“功劳大多要归到Ingineerix的头上,他花了数月才找到初始的那...

linuxCool
昨天
4
0
Gitbook : random errors when using gitbook plugin on running "gitbook serve"

在执行gitbook serve时,会有不定的失败错误 参考问题 :#1309 解决方案: 更新gitbook版本,这个问题似乎是3版本的问题 , 官方也不打算在这个版本解决了。 更新 到最新版本后, 不再出现问...

ol_O_O_lo
昨天
2
0
提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字

提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字: 作者:王健茜;断断续续一个多月才读完了《中国文化的深层结构》,这并不是一本难懂的书,之所以读得慢,源于对书中观点的思...

原创小博客
昨天
3
0
高德地图-行政区域接口

1、获取全国各省信息 https://restapi.amap.com/v3/config/district?extensions=all&key=应用Key&s=rsv3&output=json 2、获取下级行政区域信息 https://restapi.amap.com/v3/config/distric......

voole
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部