文档章节

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

侯禹
 侯禹
发布于 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
入行网络攻城狮的自述

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

柏林墙123
2017/10/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java IO类库之PrintStreamWriter

* A <code>PrintStream</code> adds functionality to another output stream, * namely the ability to print representations of various data values * conveniently. Two other fea......

老韭菜
55分钟前
0
0
qduoj~前端~二次开发~笔记

青岛大学qdu的onlinejudge是js的写的前端,框架是vue.js,在nodejs上部署运行,其实整体运行还是建立在docker的容器虚拟环境里,这里暂时不需要docker。安装环境是Ubuntu14-64bit 1.安装一大...

虚拟世界的懒猫
58分钟前
6
0
ConcurrentHashMap源码解读

部分内容转自:http://jiabinyuan.xyz/#/app/archive/detail/25 内部结构 内部采用了segment结构,每一个segment相当于一个hashtable。看下面的结构图: 从图的结构我们可以了解到,Concurr...

edwardGe
今天
1
0
Ubuntu终端Tab键自动补全

打开 /etc/bash.bashrc,找到下列代码,取消注释。 #enable bash completion in interactive shells#if ! shopt -oq posix; then# if [-f /usr/share/bash-completion/bash_compl......

大熊猫
今天
0
0
polipo socks5代理转http代理

天朝的网络,哎~ 装个 yarn 都时而会卡 假设在SSlocal 已经装好运行的前提下,来安装设置 polipo sudo apt-get install polipo sudo vim /etc/polipo/config 追加下列配置内容,并保存 socksP...

纯洁徐
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部