2011华为编程大赛第三道题

本文主要是介绍2011华为编程大赛第三道题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3、公交站寻址（50分）
问题描述
一个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: 给定的路径长度
【输出】无
【返回】能够到达的公交站个数
注：输入矩阵是以一维形式保存的二维数组，
比如输入为{‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’,’G’, ‘H’, ‘I’}，
实际上表示如下3*3的矩阵
‘A’,’B’,’C’,
‘D’,’E’,’F’,
‘G’,’H’,’I’
示例
输入："...S........X.S.....S....", 5, 3
返回：2


输入："S...S.........BS........X", 5, 5
返回：1

思路1：采用迭代，把中心情况与边角的特殊情况分开考虑。额外用一个辅助矩阵来标注哪些站点走得到。但是没有用到最短路径，走很多重复的路，非常暴力非常原始。

#include "stdafx.h"
#include "iostream"using namespace std;void SearchStat(int position, const char *Map, int *SearchedMap, int iArrN, unsigned int iPathLen)
{// 根据Map来判断if (Map[position] == 'B')	//	用于标注障碍，与标注不用走的重复路相同，在没有最短路径算法的情况下无用{SearchedMap[position] = 1;return;}if (Map[position] == 'S'){SearchedMap[position] = 2;}if (Map[position] == '.')	// 本来想用来标注哪些站点为走过站点，不走重复路的，但是发现在没有最短路径算法的情况下根本不可行{SearchedMap[position] = 1;}if (iPathLen == 0)				// 停止条件{return;}if((position % iArrN - 1) >= 0 && Map[position - 1] != 'B'){ SearchStat(position - 1, Map, SearchedMap, iArrN, iPathLen - 1);}if((position % iArrN + 1) < iArrN && Map[position + 1] != 'B'){SearchStat(position + 1, Map, SearchedMap, iArrN, iPathLen - 1);}if (position - iArrN >= 0 && Map[position - iArrN] != 'B'){SearchStat(position - iArrN, Map, SearchedMap, iArrN, iPathLen - 1);}if (position + iArrN < iArrN * iArrN && Map[position + iArrN] != 'B'){SearchStat(position + iArrN, Map, SearchedMap, iArrN, iPathLen - 1);}}int FindStat (const char *Map, unsigned int iArrN, unsigned int iPathLen)
{int position = 0;int SearchedMap[1000];for (int i = 0; i < iArrN * iArrN; i++){SearchedMap[i] = 0;}SearchedMap[iArrN * iArrN] = '\0';while (Map[position] != 'X'){position++;}SearchStat(position, Map, SearchedMap, iArrN, iPathLen);int result = 0;for (int i = 0; i < iArrN * iArrN; i++){if (SearchedMap[i] == 2){result++;}}return result;
}int _tmain(int argc, _TCHAR* argv[])
{int iArrNum,iPathLen;cout << "请输入矩阵行数：";cin >> iArrNum;/*char Map[25] = {'.', '.', '.', 'S', '.','.', '.', '.', '.', '.','.', '.', 'X', '.', 'S','.', '.', '.', '.', '.','S', '.', '.', '.', '.'};*/char Map[25] = {'S', '.', '.', '.', 'S','.', '.', '.', '.', '.','.', '.', '.', '.', 'B','S', '.', '.', '.', '.','.', '.', '.', '.', 'X'};cout << "请输入路径长度：";cin >> iPathLen;cout << "能到达的公交站数为：" << FindStat(Map, iArrNum, iPathLen);system("pause");return 0;
}

唉~~~~~~~~~~~~~~~~~~~看了别人的代码才想起可以用队列，妹夫的，我这种方法简直就是原始啊。。。

重写过。

思路2：类似于广度优先？反正是把呆行的点加入到队列中，走过的点从队列中排除差在矩阵中标注。

#include "stdafx.h"
#include "iostream"
#include "queue"using namespace std;// 思路2：类似于广度优先？反正是把呆行的点加入到队列中，走过的点从队列中排除差在矩阵中标注。int FindStat (const char *Map, unsigned int iArrN, unsigned int iPathLen)
{int result = 0;int position = 0;int SearchedMap[1000];int PathLenMap[1000];for (int i = 0; i < iArrN * iArrN; i++){SearchedMap[i] = 0;PathLenMap[i] = 0;if (Map[i] == 'X'){position = i;SearchedMap[i] = 1;}if (Map[i] == 'B'){SearchedMap[i] = 1;}}SearchedMap[iArrN * iArrN] = '\0';PathLenMap[iArrN * iArrN] = '\0';queue<int> visitedQueue;visitedQueue.push(position);while(!visitedQueue.empty()){int visitedPosition = visitedQueue.front();visitedQueue.pop();if ((visitedPosition % iArrN - 1) >= 0 && SearchedMap[visitedPosition - 1] == 0 && PathLenMap[visitedPosition] < iPathLen){SearchedMap[visitedPosition - 1] = 1;PathLenMap[visitedPosition - 1] = PathLenMap[visitedPosition] + 1;visitedQueue.push(visitedPosition - 1);if (Map[visitedPosition - 1] == 'S'){result ++;}}if ((visitedPosition % iArrN + 1) < iArrN && SearchedMap[visitedPosition + 1] == 0 && PathLenMap[visitedPosition] < iPathLen){SearchedMap[visitedPosition + 1] = 1;PathLenMap[visitedPosition + 1] = PathLenMap[visitedPosition] + 1;visitedQueue.push(visitedPosition + 1);if (Map[visitedPosition + 1] == 'S'){result ++;}}if ((visitedPosition - iArrN) >= 0 && SearchedMap[visitedPosition - iArrN] == 0 && PathLenMap[visitedPosition] < iPathLen){SearchedMap[visitedPosition - iArrN] = 1;PathLenMap[visitedPosition - iArrN] = PathLenMap[visitedPosition] + 1;visitedQueue.push(visitedPosition - iArrN);if (Map[visitedPosition - iArrN] == 'S'){result ++;}}if ((visitedPosition + iArrN) < (iArrN * iArrN) && SearchedMap[visitedPosition + iArrN] == 0 && PathLenMap[visitedPosition] < iPathLen){SearchedMap[visitedPosition + iArrN] = 1;PathLenMap[visitedPosition +iArrN] = PathLenMap[visitedPosition] + 1;visitedQueue.push(visitedPosition + iArrN);if (Map[visitedPosition + iArrN] == 'S'){result ++;}}}return result;
}int _tmain(int argc, _TCHAR* argv[])
{int iArrNum,iPathLen;cout << "请输入矩阵行数：";cin >> iArrNum;char Map[25] = {'.', '.', '.', 'S', '.','.', '.', '.', '.', '.','.', '.', 'X', '.', 'S','.', '.', '.', '.', '.','S', '.', '.', '.', '.'};/*char Map[25] = {'S', '.', '.', '.', 'S','.', '.', '.', '.', '.','.', '.', '.', '.', 'B','S', '.', '.', '.', '.','.', '.', '.', '.', 'X'};*/cout << "请输入路径长度：";cin >> iPathLen;cout << "能到达的公交站数为：" << FindStat(Map, iArrNum, iPathLen);system("pause");return 0;
}

恩，这个比较高大上了，队列！

参考资料：http://blog.csdn.net/zqt520/article/details/7460412

这篇关于2011华为编程大赛第三道题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---