[华为机试真题]73.公交站寻址

本文主要是介绍[华为机试真题]73.公交站寻址，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

一个N*N二维矩阵代表城市布局，元素值只有’.’,’X’ , ‘B’ , ‘S’，X代表当前位置，B代表路障，S代表公交站，’.’代表可行的路径。
现给定路径长度Y，找到能够到达的公交站的个数，路径中不能包含路障。
路径长度定义：
节点与其自身的距离为0
节点与其上、下、左、右四个相邻节点距离都为1

要求实现函数

int FindStat (const char *Map, unsigned int iArrN, unsigned int iPathLen)

输入

Map：           城市布局
iArrN：         城市布局矩阵的行数
iPathLen: 给定的路径长度

输出

无

能够到达的公交站个数

注：输入矩阵是以一维形式保存的二维数组，

代码

/*---------------------------------------
*   日期：2015-07-07
*   作者：SJF0115
*   题目：公交站寻址
*   来源：华为机试真题
-----------------------------------------*/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;/*
S...S
.....
....B
S...S
....X*/
// map             城市布局
// len             给定的路径长度
// index           路径的第几步
// visited         是否已经访问
// count           能够到达的公交站个数           
void DFS(vector<vector<char> > &map,int len,int index,int x,int y,vector<vector<bool> > &visited,int &count){int row = map.size();int col = map[0].size();// 超出规定路径长度if(index == len+1){return;}//if// 越界if(x < 0 || y < 0 || x >= row || y >= col){return;}//if// 路障if(map[x][y] == 'B'){return;}//if// 找到一个未曾到达的汽车站if(map[x][y] == 'S' && !visited[x][y]){visited[x][y] = true;cout<<"可以到达("<<x<<","<<y<<")汽车站"<<endl;++count;}//if// leftDFS(map,len,index+1,x,y-1,visited,count);// rightDFS(map,len,index+1,x,y+1,visited,count);// upDFS(map,len,index+1,x-1,y,visited,count);// bottomDFS(map,len,index+1,x+1,y,visited,count);//visited[x][y] = false;
}
// Map          城市布局
// row          城市布局矩阵的行数
// len          给定的路径长度
int FindStat (const char *Map, unsigned int row, unsigned int len){int size = strlen(Map);int col = size / row;// 转换为矩阵vector<vector<char> > map(row,vector<char>(col,'.'));for(int i = 0;i < size;++i){map[i / col][i % col] = Map[i];}//forint count = 0;vector<vector<bool> > visited(row,vector<bool>(col,false));// 搜索for(int j = 0;j < row;++j){for(int k = 0;k < col;++k){if(map[j][k] == 'X'){DFS(map,len,0,j,k,visited,count);break;}//if}//for}//forreturn count;
}int main(){char map[1000];int row;int len;//freopen("C:\\Users\\Administrator\\Desktop\\acm.txt","r",stdin);while(cin>>map>>row>>len){cout<<FindStat(map,row,len)<<endl;}//whilereturn 0;
}