文档章节

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

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


© 著作权归作者所有

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

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

m0_37582096 ⋅ 2017/06/01 ⋅ 0

七种css方式让一个容器水平垂直居中

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

鼎六智能 ⋅ 2016/10/17 ⋅ 0

七种CSS方式让一个容器水平垂直居中

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

山哥 ⋅ 2016/09/18 ⋅ 0

江浙沪的java春招实习综合面经

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

牛客网 ⋅ 05/26 ⋅ 0

2018年互联网技术岗(数据分析)暑期实习面试经验

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

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

入行网络攻城狮的自述

名人的经历叫做传记,网络攻城狮的叫做砖记吧O(∩_∩)O 从2016年开始才知道还有CCNA这个证,才知道网络中有一家叫做Cisco的牛逼公司 不过只要是学校开的课程我都不太感兴趣 但是看到了CCIE的...

柏林墙123 ⋅ 2017/10/21 ⋅ 0

(转)谈谈我的面经(华为、锐捷、十所、百度、腾讯、360、建行、EMC)

谈谈我的面经(华为、锐捷、十所、百度、腾讯、360、建行、EMC) 首先,感谢那些默默奉献出自己宝贵面试经验以及面试题库的童靴,你们的经验和题库让我得到很多有价值的信息,也得到丰厚了回...

颜建海 ⋅ 2014/07/06 ⋅ 3

华为二面心得 Take IT Easy!

今天刚结束了华为的面试,这应该是我为数不多的像样的面试了。虽然整个过程难度不大,但是不管怎样我都觉得接触到了另一个世界,自己开始成长了,还冒出了不少新想法。趁着熄灯睡觉前把面经敲...

陈许愿25 ⋅ 2017/05/26 ⋅ 0

华为二面心得 Take IT Easy!

今天刚结束了华为的面试,这应该是我为数不多的像样的面试了。虽然整个过程难度不大,但是不管怎样我都觉得接触到了另一个世界,自己开始成长了,还冒出了不少新想法。趁着熄灯睡觉前把面经敲...

陈许愿25 ⋅ 2017/05/25 ⋅ 0

阿里面试Java开发工程师

不得不说阿里是中国Java语言 技术最牛逼的一家互联网公司。 去年在润和出来的时候 心想技术还不错了,应该可以试试阿里巴巴的Java岗位,他写的jd 我一般都可以符合了。当然润和是一家外包公司...

杨中仁 ⋅ 2016/09/22 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

容器之重命名镜像

使用docker tag命令来重命名镜像名称,先执行help,查看如何使用如下 mjduan@mjduandeMacBook-Pro:~/Docker % docker tag --helpUsage:docker tag SOURCE_IMAGE[:TAG] TARGET_IMAGE[:TA...

汉斯-冯-拉特 ⋅ 18分钟前 ⋅ 0

with 的高级用法

那么 上下文管理器 又是什么呢? 上下文管理器协议包含 __enter__ 和 __exit__ 两个方法。with 语句开始运行时,会在上下文管理器对象上调用 __enter__ 方法。with 语句运行结束后,会在上下...

阿豪boy ⋅ 37分钟前 ⋅ 0

使用 jsoup 模拟登录 urp 教务系统

需要的 jsoup 相关 jar包:https://www.lanzous.com/i1abckj 1、首先打开教务系统的登录页面,F12 开启浏览器调试,注意一下 Request Headers 一栏的 Cookie 选项,我们一会需要拿这个 Cook...

大灰狼时间 ⋅ 37分钟前 ⋅ 0

关于线程的创建

转自自己的笔记: http://note.youdao.com/noteshare?id=87584d4874acdeaf4aa027bdc9cb7324&sub=B49E8956E145476191C3FD1E4AB40DFA 1.创建线程的方法 Java使用Thread类代表线程,所有的线程对......

MarinJ_Shao ⋅ 48分钟前 ⋅ 0

工厂模式学习

1. 参考资料 工厂模式-伯乐在线 三种工厂-思否 深入理解工厂模式 2. 知识点理解 2.1 java三种工厂 简单工厂 工厂模式 抽象工厂 2.2 异同点 逐级复杂 简单工厂通过构造时传入的标识来生产产品...

liuyan_lc ⋅ 今天 ⋅ 0

Java NIO

1.目录 Java IO的历史 Java NIO之Channel Java NIO之Buffer Java NIO之Selector Java NIO之文件处理 Java NIO之Charset Java 可扩展IO 2.简介 “IO的历史”讲述了Java IO API从开始到现在的发...

士别三日 ⋅ 今天 ⋅ 0

[Err] ORA-24344: success with compilation error

从txt文本复制出创建function的脚本,直接执行,然后报错:[Err] ORA-24344: success with compilation error。 突然发现脚本的关键字,居然不是高亮显示。 然后我把脚本前面的空格去掉,执行...

wenzhizhon ⋅ 今天 ⋅ 0

Spring Security授权过程

前言 本文是接上一章Spring Security认证过程进一步分析Spring Security用户名密码登录授权是如何实现得; 类图 调试过程 使用debug方式启动https://github.com/longfeizheng/logback该项目,...

hutaishi ⋅ 今天 ⋅ 0

HAProxy基于KeepAlived实现Web高可用及动静分离

前言 软件负载均衡一般通过两种方式来实现: 基于操作系统的软负载实现 基于第三方应用的软负载实现 LVS是基于Linux操作系统实现的一种软负载,而HAProxy则是基于第三方应用实现的软负载。 ...

寰宇01 ⋅ 今天 ⋅ 0

微软自研处理器的小动作:已经开始移植其他平台的工具链

微软将 Windows 10 、Linux 以及工具链如 C/C++ 和 .NET Core 运行时库、Visual C++ 2017 命令行工具、RyuJIT 编辑器等移植到其自主研发的处理器架构 E2。微软还移植了广泛使用的 LLVM C/C++...

linux-tao ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部