#include <iostream>
#include <utility>
#include <queue>
#include <stack>
using namespace std;
const int SPACE=0;
const int WALL=1;
bool bFinish;
int Path[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
int M[5][5]={{0,1,1,1,0},
             {0,0,0,0,0},
             {0,1,0,0,1},
             {0,1,0,0,0},
             {0,1,1,1,0}};

bool fnIsInSide(int a,int b){
    return (a>=0&&a<=4&&b>=0&&b<=4);
}

int fnBfs(){
    queue<pair<int,int> >MyQ;
    int nX,nY,nCnt=1;
    pair<int,int>MyP_A,MyP_B;
    MyP_A.first=0;
    MyP_A.second=0;
    MyQ.push(MyP_A);
    while(!MyQ.empty())
    {
        MyP_A=MyQ.front();
        ++nCnt;
        if(MyP_A.first==4&&MyP_A.second==4)
            return ++bFinish;
        MyQ.pop();
        M[MyP_A.first][MyP_A.second]=WALL;
        for(int i=0;i<4;++i)
        {
            nX=MyP_A.first+Path[i][0];
            nY=MyP_A.second+Path[i][1];
            if(fnIsInSide(nX,nY)&&M[nX][nY]!=WALL)
            {
                MyP_B.first=nX;
                MyP_B.second=nY;
                MyQ.push(MyP_B);
            }
        }
    }
    return bFinish;
}

void fnDfs(int x,int y){
    int nX,nY;
    if(x==4&&y==4) ++bFinish;
    if(bFinish) return;
    for(int i=0;i<4;++i)
    {
        nX=x+Path[i][0];
        nY=y+Path[i][1];
        if(fnIsInSide(nX,nY)&&M[nX][nY]!=WALL)
        {
            M[nX][nY]=WALL;
            fnDfs(nX,nY);
            M[nX][nY]=SPACE;
        }
    }
}

int main(){
    int hWay;
    cout<<"If you want Breadth First Search ,input(0),else input(1) -- Depth First Search."<<endl;
    cin>>hWay;
    hWay?fnDfs(0,0):(void)fnBfs();
    bFinish?cout<<"The path is found."<<endl:cout<<"The path isn't found"<<endl;
    return 0;
}

/*
cin>>hWay;
hWay?fnDfs(0,0):fnBfs();

2个函数
void fnDfs(0,0);
int fnBfs();
不懂为什么G++ 编译器提示
error: `fnDfs(0, 0)' has type `void' and is not a throw-expression

原来这里必须
A?B:C
条件操作符B和C要有相同的类型或者可以相互转化
你的一个void，一个int肯定不行

The rule is: if one the operand is of type void, then the other
| > operand must be of type void or a throw expression -- but both cannot
| > be a throw-expression.
*/