题目描述：
在一个迷宫里面有一只小狗发现了一根骨头，现在他准备逃出迷宫，迷宫中只有一个地方有门可以出去，而且这个门只会在T秒的时候打开，开了之后下一时刻就会关闭。每移动一步要花费1秒，规定不能停留在某一个位置上，即走到一个位置要立刻前往下一个位置。每个位置不能重复走。假设小狗很聪明，它能成功逃出迷宫么？
输入格式：
第一行输入三个整数n,m,T,表示迷宫的尺寸以及门打开的时间
接下来n行每行m个字符，表示迷宫中每一个位置上的信息。
‘X’: 表示墙，不能进入
‘S’: 小狗现在的位置
‘D’: 门
‘.’: 空地
输出格式：
根据能否成功逃离，输出“YES” 或者“NO”
样例输入1：
4 4 5
S.X.
. .X.
. .XD
. . . .
样例输出1：
NO
插一个题外话：上一篇写完后同学说我水题解，这次我发誓找不到更详细的题解。
//先写输入
int main()
{
cin>>n>>m>>T;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='D'){ //门的位置
ex=i;
ey=j;
}
if(a[i][j]=='S'){ //狗的位置
sx=i;
sy=j;
}
}
}
return 0;
}
因为这题地图不大，maxn（范围常量）为十就行
const int maxn = 10;
int n,m,T;
int main(){
……
}
这里要一个剪枝
for(i:1~n){
for(j:1~m){
cin>>a[i][j]
}
}
if(ex+ey+sx+sy+T&1){
cout<<"NO";exit(0);
}
//这个是奇偶性剪枝，具体解释在下方。
//然后加判定输出
if（……）{
……
}
if(dfs(sx,sy,0)){
cout<<"YES";
}else{
cout<<"NO";
}
接下来只剩dfs了
//接下来一堆定义
int dx[4] = { 1, 0, -1, 0 };//定义方向数组
int dy[4] = { 0, 1, 0, -1 };
bool dfs（int x,int y,int t）{}//定义dfs
if( abs(x - ex) + abs(y - ey) > T) {
//cout<<0<<" ";
return false;
}//定义剪枝
dfs里不具体写了，具体点击这里
这里讲一下剪枝原理：曼哈顿距离
曼哈顿距离=|x1-x2|+|y1-y2|
是在只能走直线的前提下的最短路径
现在就讲完了，理论上应该会写了
不会的看下方
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10;
int n,m,T;char a[maxn][maxn];
int ex,ey,sx,sy;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
bool vis[maxn][maxn],mp[maxn][maxn];
bool dfs(int x,int y,int t){
if( abs(x - ex) + abs(y - ey) > T) {
return false;
}
if( x==ex&&y==ey&&t==T)
{
return true;
}
bool cnt;
for(int i = 0;i < 4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m ) {
if((!vis[nx][ny]) && a[nx][ny]=='.'||a[nx][ny]=='D'){
vis[nx][ny]=true;
cnt=cnt||dfs(nx,ny,t+1);
mp[nx][ny]==1;
vis[nx][ny]=false;
}
}
}
return cnt;
};
int main()
{
cin>>n>>m>>T;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='D'){
ex=i;
ey=j;
}
if(a[i][j]=='S'){
sx=i;
sy=j;
}
}
}
if(ex+ey+sx+sy+T&1){
cout<<"NO";exit(0);
}
if(dfs(sx,sy,0)){
cout<<"YES";
}else{
cout<<"NO";
}
return 0;
}
如果觉得详细的话就点个赞呗。 