原题：

胜利大逃亡

题目描述

$elfness$被魔王抓走了，这次魔王把$elfness$关在一个$n*m$的地牢里。地牢的某个地方安装了一个带锁的门，钥匙藏在地牢的另外一个地方，$elfness$想要通过这个门，就必须先走到藏钥匙的地方取钥匙。刚开始的时候$elfness$被关在$(sx,sy)$的位置，而离开地牢的门在$(ex,ey)$的位置。$elfness$每分钟只能从一个位置走到相邻四个位置中的其中一个。魔王每$t$分钟都回地牢视察一次，若发现$elfness$不在原位置便会把他拎回去。经过若干次的尝试，$elfness$已经画出了整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候还未到出口都算逃亡失败。注意，逃跑路线不一定非要通过带锁的门。

输入格式

第一行有三个整数$n,m,t$。接下来的$n$行$m$列为地牢的地图，其中包括:

$.$ 代表路

$*$代表墙

$@$ 代表$elfness$的起始位置

^ 代表地牢的出口

$A$ 代表带锁的门

$a$ 代表钥匙

输出格式

一行，包含一个整数。对于可以成功逃亡的情况，请输出至少需要多少分钟才能离开，如果不能则输出$-1$。

样例 #1

样例输入 #1

4 4 100
@..A
a.*.
***.
^...

样例输出 #1

11

提示

数据范围

对于$50\%$的数据，地牢没有带锁的门和钥匙

对于$100\%$的数据，$2<=n,m<=20，t>0$

40pts代码：

#include<bits/stdc++.h>
using namespace std;
int mn=99999;					
int c[4][2]={{1,0},{0,1},{-1,0},{0,-1}};	//这里是定义的四个方向，上下左右
int n,m,t,mx,my,cx,cy,vis[105][105],sx,sy,dx,dy;
char s[100][100];		
void dfs(int x,int y,int step,char mdd)		
{
    int i,xn,yn;
    if(s[x][y]==mdd)				
    {								
        if(step<mn)	
            mn=step;
        return;
    }
    for(i=0; i<4; i++)		
    {
        xn=x+c[i][0];	
        yn=y+c[i][1];	
        if(xn<=0||xn>n||yn<=0||yn>m)	
        {
            continue;					
        }
        if(s[xn][yn]!='*'&&vis[xn][yn]==0)			
        {
            vis[xn][yn]=1;					
            dfs(xn,yn,step+1,mdd);		
            vis[xn][yn]=0;			
        }
    }
    return;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>s[i][j];
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {          
            if(s[i][j]=='@')cx=i,cy=j;
            if(s[i][j]=='a')sx=i,sy=j;          
        }
    }
    vis[cx][cy]=1;
    dfs(cx,cy,0,'^');
    int damen=mn;
    mn=99999;
    memset(vis,0,sizeof(vis));
    dfs(cx,cy,0,'a');
    int suo1=mn;
    memset(vis,0,sizeof(vis));
    mn=99999;
    dfs(sx,sy,0,'A');
    int suo2=mn;
    if(min(suo1+suo2,damen)>t||(damen==99999&&(suo1==99999||suo2==99999)))cout<<-1;
    else cout<<min(suo1+suo2,damen);

}

评测：https://www.luogu.com.cn/record/80106378