学步园

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

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;


void bfs(int des,int *path,int *if_vis,const char *Map,int iArrN);

int FindStat (const char *Map, unsigned int iArrN, unsigned int iPathLen)
{
	
	int len = iArrN*iArrN,i;
	int *path = (int *)malloc(len*sizeof(int));
	int *if_vis = (int *)malloc(sizeof(int)*len);
	int num = 0;
	memset(path,-1,len*sizeof(int));
	memset(if_vis,0,len*sizeof(int));
	
	int des = strchr(Map,'X') - Map;
	
    bfs(des,path,if_vis,Map,iArrN);
	
	for(i=0;i<len;i++)
	{
		printf("%d%c   ",path[i],Map[i]);
		if(!((i+1)%iArrN))
			printf("\n");
	}
	
	for(i=0;i<len;i++)
	{
        if(path[i] <= iPathLen && Map[i] == 'S')
			num++;
	}
    return num;
}

int main()
{
	
	char *map = "S.B.S..B.B...B.S...B..B.X";
	unsigned int iArrN = 5;
	unsigned int iPathLen = 5;
	
	
	printf("%d\n",FindStat(map,iArrN,iPathLen));
	
	
	return 0;
}

void bfs(int des,int *path,int *if_vis,const char *Map,int iArrN)
{
	
	queue<int> q;
	q.push(des);
	path[des] = 0;
	if_vis[des] = 1;
	while(!q.empty())
	{
		int pos = q.front();
		q.pop();
		
		
		//上
		int up = pos - iArrN;
		
		if(up>=0 && Map[up] != 'B' && !if_vis[up])
		{
			if_vis[up] = 1;
			path[up] = path[pos]+1;
			q.push(up);
		}
		
		//下
		int down = pos + iArrN;
		
		if(down <= iArrN*iArrN-1 && Map[down] != 'B' && !if_vis[down])
		{
			if_vis[down] = 1;
			path[down] = path[pos]+1;
			q.push(down);
		}
		
		//左
		int left = pos - 1;
		if(pos%iArrN > 0)
		{
			if(left >= 0 && Map[left] != 'B' && !if_vis[left])
			{
				if_vis[left] = 1;
				path[left] = path[pos]+1;
				q.push(left);
			}
		}
		//右
		int right = pos + 1;
		if(pos%iArrN < iArrN-1)
		{
			if(right <= iArrN*iArrN-1 && Map[right] != 'B' && !if_vis[right])
			{
				if_vis[right] = 1;
				path[right] = path[pos]+1;
				q.push(right);
			}
		}
		
	}
}

思想：bfs矩阵，更新距离，障碍或由于障碍未能访问到的点距离为-1，最后找出所有符合条件的公交站。新手，欢迎大家批评指正。