资源描述：
《微软笔试题范文》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、微软笔试题范文 为一个优秀的程序猿我们自然要懂一些叼叼的算法今天给大家介绍的就是微软的一道线上笔试题的解析 Description EverydayLittileHiandLittleHomeetintheschoolcafeteriatohavelunchtogether.Thecafeteriaisoftensocrowdedthattwoadjacentseatsarehardtofind. SchoolcafeteriacanbeconsideredasamatrixofN*Mblocks.Ea
2、chblockcanbeemptyoroccupiedbypeople,obstructionsandseats.LittleHiandLittleHostartsfromthesameblock.Theyneedtofindtwoadjacentseats(twoseatsareadjacentifandonlyiftheirblocksshareamonedge)withoutpassingthroughoccupiedblocks.Furthermore,theywantthetotaldistancetotheseat
3、sisminimal. LittleHiandLittleHocanmovein4directions(up,down,left,right)andtheycannotmoveoutsidethematrix. 题意分析 给定一幅字符表示的地图其中包含有1个起点'H'若干个座位'S'墙壁''和行人'P' 其中墙壁''和行人'P'是不可通过的区域 假设在地图中只能沿着上下左右移动且每移动一个单元格为1步 询问从'H'点出发是否能够到达两个相邻的'S'且需要移动的步数最少是多少 算法分析
4、 从题目当中我们就可以知道本题需要做什么： 读取字符地图并找到起点的位置 从起点开始遍历该地图记录到达每一个'S'的距离 判断是否有两个相邻的'S'都可达若存在多个解则需要找到最小的值 那么我们就按照这三个步骤来解决这道题目 首先是数据的读入由于输入数据中已经明确的告诉了我们地图为N行M列所以我们只需要一行一行读入字符串并使用charmap[N][M]保存该地图 map[i][j]表示原地图的第i行第j列的信息 之后再对整个map[i][j]进行一次O(mn)的遍历找出起点的位置并
5、记录下来 我们用startX,startY来记录起点的坐标 startX=startY=0; //读入地图 for(inti=1;i<=N;i++) scanf(%s,map[i]+1); //查找起点H for(inti=1;i<=N;i++) for(intj=1;j<=M;++j) if(map[i][j]=='H'){ startX=i,startY=j; break; } 第二步寻找从起点(startX,startY)分别到每个'S'的最短
6、路径这一步我们直接使用BFS对整个图进行一次遍历 首先建立数组intstep[N][M]step[i][j]表示从起点到(i,j)的最少步数 初始化为step[i][j]=INTMAX默认为任何点都无法到达 开始遍历时将step[startX][startY]设定为0并以(startX,startY)开始BFS整个地图 在遍历整个地图的过程中我们需要注意： 当map[i][j]=''或map[i][j]='P'时step[i][j]直接等于INTMAX并且不扩展新的节点 当map[i][j]
7、='S'时我们需要更新当前节点的step[i][j]信息但是由于当小Hi和小Ho走到位置后就不会再进行移动所以也不扩展新的节点 最后当没有新的节点可以到达时退出BFS得到整个地图的step[N][M] boolinMap(intx,inty){ //在地图内不为墙壁同时也不为行人 return(1<=xx<=N1<=yy<=M)(map[x][y]=='.'
8、
9、map[x][y]=='S'); } constintdir[4][2]={{0,1},{1,0},{0,1},{1,0}};//方
10、向数组 vectorseq;//用一个vector来存储BFS的队列 voidBFS(intstartX,intstartY){ //将起点存入队列 step[startX][startY]=0; seq.pushback(makepair(st
