简单的深搜

2019-12-02

难受啊，马飞

老实讲，我不想写深搜了。但是一想到这题就难受啊。

这题就是简单的深搜，本来AC了，新生赛就从铜牌成金牌，还能白嫖一本算法书。但是，现在想起来是真的气哦。输出的时候 s > t 写成 s > 3 ,不是，这 3 哪来的，我 t m 人都傻了（wa了7次，当时可能懵了）。越想越气，难受啊！

6119: 学长的阴谋

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte总提交: 74 测试通过:17

异世界穿越到现代华夏的魔王在面对科技发达的现代社会，完全迷失了人生的方向。为了不继续颓废下去而玷污了他魔王的名声，他决定干回本职工作——抓公主！当然，在现代华夏是不存在公主这个身份的，于是，魔王退而求其次，抓走了众人爱戴的学姐，随后利用魔王的力量创造了高耸的城堡，将学姐关在城堡的顶层。深爱着学姐的nzh得知学姐被抓走的事情后悲痛欲绝，他决心化身勇者，潜入魔王的栖身之所，只身一人救出学姐。

nzh通过现代技术探明了魔王所在的城堡并绘制了地图，城堡由下至上有许多层，每层都是一个迷宫，每层迷宫只有一个出口可以抵达上一层迷宫，而学姐就被关在最顶层的某处。不幸的是，nzh勇武有余而智谋不足，他不知道应该怎么走抵达最上层，现在，他请求同样深爱着学姐的你的帮助，你需要规划并且告诉nzh，他需要走怎样的路线才能解救学姐。

事实上，魔王抓走学姐正是你给魔王出的主意，你与初到现代的魔王做了一笔交易，你教会魔王现代知识并且帮助魔王占领世界，而魔王则帮助你除掉情敌nzh，并且帮你上演一出正义勇者战胜魔王拯救学姐的戏码。因此你安排魔王亲自守护在学姐的栖身之所，同时帮助nzh规划路线，让nzh能够顺利出现在魔王的面前，借魔王之手干掉他。

啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈咳咳呃。 ——某情敌

输入

第一行包含两个整数T，n。

T迷宫的层数。（T<=20）

n表示每层迷宫的大小，迷宫由一个n*n的区域组成。（2<=n<=100）

接下有T组nn的字符，第一组nn的字符表示第一层的迷宫，第二组表示第二层。

字符由’S’，’P’，’#’，’B’，’.’组成，其中

‘S’表示每层迷宫的起点。

‘P’表示每层迷宫的终点。

‘B’表示最后一层魔王的位置。

‘#’表示墙壁不可通过。

‘.’表示通道可以通过。

最后一层迷宫只存在魔王’B’而不存在终点’P’。

一开始nzh处于城堡的第一层，且仅能走前后左右四个方向，不能斜着走。

输出

对于每组数据输出两行，第一行输出nzh最后可以抵达的迷宫的层数，第二行有两种情况，如果nzh无法达到学姐所在地，输出“sorry, my love!”，如果他成功抵达学姐所在地，则输出“oh, no!”。

样例输入

3 3

S..
…
..P
..P
…
S..

…

S.B

…

样例输出

3
oh, no!

#include <bits/stdc++.h>

using namespace std;

char q[105][105];
int x[]={1,-1,0,0};
int y[]={0,0,1,-1};
int sx,sy,px,py,bx,by;
int f,n,t,ce;
void dfs(int xx,int yy)
{
    if((xx==px && yy==py && ce<t) || (xx==bx && yy==by && ce == t))
    {
        f=1;
        return ;
    }
    for(int i=0;i<4;i++)
    {
        int dx=xx+x[i];
        int dy=yy+y[i];
        if(dx<n && dx>=0 && dy<n && dy>=0 && q[dx][dy]!='#' )
        {
            q[dx][dy]='#';
            dfs(dx,dy);
            //cout<<dx<<" "<<dy<<" "<<f<< endl;

        }

    }
}
int main()
{
    while(cin>>t>>n)
    {
        int s=1;
        int c[25];
        for(int k=0;k<t;k++)
        {
            f=0;ce=k+1;
            for(int i=0;i<n;i++)
            {
                getchar();
                for(int j=0;j<n;j++)
                {
                    q[i][j]=getchar();
                    if(q[i][j]=='S')sx=i,sy=j;
                    else if(q[i][j]=='P')px=i,py=j;
                    else if(q[i][j]=='B')bx=i,by=j;
                }
            }
            dfs(sx,sy);
            c[k]=f;
        }
        for(int i=0;i<t;i++)
        {
            if(c[i]==0)break;
            s+=c[i];
        }

        if(s>t)printf("%d\n",t);  //就是这里，写成 S > 3 ,输出 3 . 难受啊 
        else printf("%d\n",s);
        if(s>t)printf("oh, no!\n");
        else printf("sorry, my love!\n");
    }
    return 0;
}