Jack拆炸弹

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

在一个由n*n个格子组成的监狱里被恐怖份子安置了一个定时炸弹。其中，连续的“.”表示格子之间可以通行，“#”表示障碍物。每次只能按上下左右4个方向走，有障碍物就不能通过。给出一副监狱的俯视图和炸弹(B)和侦探Jack(P)的位置，问Jack能不能找到炸弹的安置点并及时把它拆除，若可以输出"Yes",否则输出“No”.

Input:

输入包含多组测试数据，每组数据第一行为一整数n（n<=100）,接着以方格形式输入n*n个字符。

Output:

对于每组测试数据，输出为一行，若Jack可以找到炸弹输出"Yes",否则输出“No”.

Sample Input:

4#.P..#...##..B..8#.#....PB#....#..#......#......#.#....#.#....###.##.....#......#

Sample Output:

YesNo 解题思路：还是简单的深搜，水过！ AC代码（7ms）：

1 #include
      
        2 using namespace std; 3 int si,sj,n,dir[4][2]={
    {-1,0},{
    0,1},{
    1,0},{
    0,-1}};char msp[105][105];bool flag; 4 void dfs(int x,int y){ 5     if(x<0||y<0||x>=n||y>=n||msp[x][y]=='#')return; 6     if(msp[x][y]=='B'){flag=true;return;}//找到'B'，则直接返回 7     msp[x][y]='#';//将走过的点标记为'#'，表示不能再走 8     for(int i=0;i<4;++i){ 9         dfs(x+dir[i][0],y+dir[i][1]);10         if(flag)return;//如果找到，则直接返回11     }12 }13 int main(){14     while(~scanf("%d",&n)){15         for(int i=0;i