文档章节

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

侯禹
 侯禹
发布于 2013/09/08 00:05
字数 940
阅读 76
收藏 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;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 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:auto 方法六......

鼎六智能
2016/10/17
28
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
江浙沪的java春招实习综合面经

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

牛客网
05/26
0
0
2018年互联网技术岗(数据分析)暑期实习面试经验

此经验帖适合想找互联网相关工作的人,如数据分析、算法工程师、数据挖掘工程师等。或者是想进入BAT等互联网公司的人,我会介绍他们暑期实习招聘流程及笔面试经验等,暑期实习往往是有转正机...

你的社交帐号昵
05/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

可爱的python测试开发库(python测试开发工具库汇总)

欢迎转载,转载请注明来源: github地址 谢谢点赞 本文地址 相关书籍下载 测试开发 Web UI测试自动化 splinter - web UI测试工具,基于selnium封装。 链接 selenium - web UI自动化测试。 链...

python测试开发人工智能安全
今天
2
0
Shiro | 实现权限验证完整版

写在前面的话 提及权限,就会想到安全,是一个十分棘手的话题。这里只是作为学校Shiro的一个记录,而不是,权限就应该这样设计之类的。 Shiro框架 1、Shiro是基于Apache开源的强大灵活的开源...

冯文议
今天
1
0
linux 系统的运行级别

运行级别 运行级别 | 含义 0 关机 1 单用户模式,可以想象为windows 的安全模式,主要用于修复系统 2 不完全的命令模式,不含NFS服务 3 完全的命令行模式,就是标准的字符界面 4 系统保留 5 ...

Linux学习笔记
今天
2
0
学习设计模式——命令模式

任何模式的出现,都是为了解决一些特定的场景的耦合问题,以达到对修改封闭,对扩展开放的效果。命令模式也不例外: 命令模式是为了解决命令的请求者和命令的实现者之间的耦合关系。 解决了这...

江左煤郎
今天
3
0
字典树收集(非线程安全,后续做线程安全改进)

将500W个单词放进一个数据结构进行存储,然后进行快速比对,判断一个单词是不是这个500W单词之中的;来了一个单词前缀,给出500w个单词中有多少个单词是该前缀. 1、这个需求首先需要设计好数据结...

算法之名
昨天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部