/*
   例题在网上都可以搜到

   笨笨熊搬家之交通篇
问题描述:
森林里的笨笨熊要乔迁新居，他已经将物品打包完成，并约了朋友来帮忙。接下来他要选定一个搬家的时间，想了很久，就决定在国庆节进行，因为国庆放假朋友们都有时间啦。但是在森林里，从他现在房子到豪宅，所经之地有山有水，路途曲折，甚至有些道路是不能的。
请你和他一起查看指定的地图，看看从笨笨熊现在的房子到新宅之间，道路是否畅通呢？
地图是R行、C列的矩阵，矩阵的每一个格子刚好是一天的行程。
B：代表笨笨熊现在的房子；
H：代表笨笨熊新的豪宅；
-：代表可以通行的道路；
#：代表无法通过的障碍（高山、大河等）；
此外，森林里也有交通规则：在任务位置，只能向“上、下、左、右”四个方向的其中一个方向行走。
运行时间：无限制
内    存：无限制
输    入：
4  // R的数值
7  // C的数值，下面是地图。
-       -       #       #       -       -       -
B       -       -       -       -       -       H
#       -       -       -       #       -       -
-       -       -       -       -       -       -

*/

/*
    Name: 19-1-clumsyBearMoving-1.
    Date: 02/11/19 08:30
    Description: 只输出能否到达 
*/

/*深度优先搜索*/
#include<iostream>
#include<queue>
#include<vector>

using namespace std;
struct Node{
    int x;
    int y;
    char state;
    int visited;
};

vector<vector<Node> > map;//定义二维数组，存储地图 
int r,c,sx,sy;//r:row 行 c:column 列 sx:start x sy start y
void CrtMap(){
    Node n;
    cin>>r>>c;
    map.resize(r+1,vector<Node>(c+1));
    for(int i=1;i<=r;i++) 
    for(int j=1;j<=c;j++)
    {
        cin>>map[i][j].state;
        map[i][j].x=i;
        map[i][j].y=j;
        map[i][j].visited=0;//初始化为0
        if(map[i][j].state=='B'){//寻找起点 
            sx=i;
            sy=j;
        } 
    }
}
int IsAchieved;
void DFS(int sx,int sy)//广度优先搜索
{
    map[sx][sy].visited=1;
    if(map[sx][sy].state=='H')
    {
        IsAchieved=1;
        return;
    }

    int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    //类似于一次函数
    //上下左右走的坐标变化
    int nx,ny;
    for(int i=0;i<4;i++)
    {
        nx=map[sx][sy].x+dir[i][0];//nx:next node x
        ny=map[sx][sy].y+dir[i][1];//ny:next node y
        if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&map[nx][ny].state!='#'&&map[nx][ny].visited!=1){//判断是否到达边界
         DFS(nx,ny);
        }
    } 
} 


void OutMap() {//输出地图检查 
    for(int i=1;i<=r;i++) {
        for(int j=1;j<=c;j++)
    {
        cout<<map[i][j].state;
    }cout<<endl;
    }

}

int main()
{
    CrtMap();
    OutMap();

    printf("sx=%d sy=%d\n",sx,sy);//寻找起点
    DFS(sx,sy);
    IsAchieved==1?printf("Yes"):printf("No"); 
    return 0;
}

/*广度优先搜索*/
#include<iostream>
#include<queue>
#include<vector>

using namespace std;
struct Node{
    int x;
    int y;
    char state;
    int visited;
};

vector<vector<Node> > map;//定义二维数组，存储地图 
int r,c,sx,sy;//r:row 行 c:column 列 sx:start x sy start y
void CrtMap(){
    Node n;
    cin>>r>>c;
    map.resize(r+1,vector<Node>(c+1));
    for(int i=1;i<=r;i++) 
    for(int j=1;j<=c;j++)
    {
        cin>>map[i][j].state;
        map[i][j].x=i;
        map[i][j].y=j;
        map[i][j].visited=0;//初始化为0
        if(map[i][j].state=='B'){//寻找起点 
            sx=i;
            sy=j;
        } 
    }
}
int IsAchieved;
void BFS()
{
    queue<Node> q;
    Node cn;//current node
    //同DFS
    map[sx][sy].visited=1;
    q.push(map[sx][sy]);
    int nx,ny,cx,cy;
    int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    while(!q.empty())
    {
        cn=q.front();
        q.pop();
        sx=cn.x ;
        sy=cn.y ;
        for(int i=0;i<4;i++){
        nx=map[sx][sy].x+dir[i][0];//nx:next node x
        ny=map[sx][sy].y+dir[i][1];//ny:next node y
        if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&map[nx][ny].state!='#'&&map[nx][ny].visited!=1){//判断是否到达边界
        if(map[nx][ny].state=='H')
        {
            IsAchieved=1;
            return;
        }
        map[nx][ny].visited=1;
        q.push(map[nx][ny]);
            }
        } 
    }

    }

void OutMap() {//输出地图检查 
    for(int i=1;i<=r;i++) {
        for(int j=1;j<=c;j++)
    {
        cout<<map[i][j].state;
    }cout<<endl;
    }

}

int main()
{

    CrtMap();
    OutMap();

    printf("sx=%d sy=%d\n",sx,sy);//寻找起点
    BFS();
    IsAchieved==1?printf("Yes"):printf("No"); 
    return 0;
}

本蒟蒻首次发分享，不足之处请大佬指正
*/