CodingNote/isPathExist.cpp at master · panoshu/CodingNote · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
using namespace std;

bool find_Char(const vector<vector<char> > &vec, char ch, int &row, int &col)
{
    for(vector<char>::size_type r = 0; r != vec.size(); ++r)
    {
        for(vector<char>::size_type c = 0; c != vec[r].size(); ++c)
        {
            if(vec[r][c] == ch)
            {
                row = r;
                col = c;
                return true;
            }
        }
    }
    return false;
}

bool find_path(vector<vector<char> > &vec, vector<char>::size_type row, vector<char>::size_type col, char target)
{
    if(row < 0 || col < 0 || row >= vec.size()
       || col >= vec[vec.size()-1].size())
    {
        return false;
    }

    if(vec[row][col] == target)
    {
        return true;
    }

    if(vec[row][col] == '#')
    {
        return false;
    }

    char temp = vec[row][col];
    vec[row][col] = '#';

    if( find_path(vec, row, col-1, target) )
        return true;
    if( find_path(vec, row, col+1, target) )
        return true;
    if( find_path(vec, row-1, col, target) )
        return true;
    if( find_path(vec, row+1, col, target) )
        return true;

    vec[row][col] = temp;
    return false;
}

int main()
{
    vector<char>::size_type row(0),col(0);
    cin>>row>>col;

    vector<vector<char> > vec_map(row);
    for(vector<char>::size_type r = 0; r != row; ++r)
    {
        vec_map[r].resize(col);
        for(vector<char>::size_type c =0; c != col; ++c)
        {
            char cVar(0);
            cin>>cVar;
            vec_map[r][c] = cVar;
        }
    }

    int row_B(0), col_B(0);
    char result = 'N';
    if(find_Char(vec_map, 'B', row_B, col_B))
    {
        result = find_path(vec_map, row_B, col_B, 'H')?'Y':'N';
    }
    cout<<result<<endl;

    return 0;
}