【华为上机题】森林小熊寻路

本文主要是介绍【华为上机题】森林小熊寻路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述：小熊要在一个R*C维矩阵形状的森林里从B点出发，执行任务，到H点去，在森林里有可能会存在小溪等障碍物（用“#”表示），畅通的路径点用“-”表示，森林里面行走规则：只能向前后左右四个方向行走，现在问小熊能否成功的完成任务，若能，则输出YES，否则输出NO。

输入：

R

C

--#--#

B----H

#--#--

输出：

成功：YES

失败：NO

输入示例：

3

3

###

B-H

###

输出：

YES

1

5

B---H

输出：

YES

思想：建立一个R*C维bool数组，对应于矩阵中的每一个点，只有当点时“#”是，取值为false，其余情况均取值为true，从B点递归的判断B的上下左右四个点的状态，在每次递归前都得将已走过的路径点置为false，以防止重复走向相同的路径点，当判定到当前点出了矩阵边界或者为障碍物时则返回false,当已经到达H点时，返回true。

#include<iostream>
using namespace std;
bool isAble(bool **flag,int R,int C,int bi,int bj,int hi,int hj){if(bi<0||bj<0||bi>=R||bj>=C)//出矩阵边界时return false;if(flag[bi][bj]==false)//已访问过或者当前点为障碍物时return false;if(bi==hi&&bj==hj)return true;flag[bi][bj]=false;//当前点已走过，将其置为falsebool up=isAble(flag,R,C,bi-1,bj,hi,hj);//向上走是否可行bool down=isAble(flag,R,C,bi+1,bj,hi,hj);//向下走是否可行bool left=isAble(flag,R,C,bi,bj-1,hi,hj);//向左走是否可行bool right=isAble(flag,R,C,bi,bj+1,hi,hj);//向右走是否可行return up||down||left||right;//只要有一条路径可行则可以到达
}int main(void){while(true){int R,C;int bi,bj,hi,hj;cin>>R>>C;char ch;bool **flag = new bool*[R];for(int i=0;i<R;i++){flag[i]=new bool[C]; }for(int i=0;i<R;i++)for(int j=0;j<C;j++){cin>>ch;if(ch=='#')flag[i][j]=false;else {flag[i][j]=true;if(ch=='B'){bi=i;bj=j;}if(ch=='H'){hi=i;hj=j;}}}if(isAble(flag,R,C,bi,bj,hi,hj))cout<<"YES"<<endl;elsecout<<"NO"<<endl;system("pause");delete[] flag;}	return 0;
}

这篇关于【华为上机题】森林小熊寻路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---