题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2102点击打开链接

A计划

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 22102    Accepted Submission(s): 5563 Problem Description 可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。 现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。   Input 输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。   Output 如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。   Sample Input 1 5 5 14 S*#*. .#... ..... ****. ...#. ..*.P #.*.. ***.. ...*. *.#..   Sample Output YES  

大概意思就是在t时间内到达p点 #是传送门 到达另一层 不需要耗费时间 

step记录步数 并且当前步数若大于等于step步数则return 注意需要等于 不然会T

深搜做法 

#include <stdio.h> #include <stdlib.h> #include <iostream> #include<algorithm> #include <math.h> #include <string.h> #include <limits.h> #include <string> #include <queue> #include <stack> using namespace std; int n=0; int m=0; char a[2][11][11]; int book[2][11][11]; int step[2][11][11]; int num=0; int flag=0; int xx,yy,zz; void dfs(int x,int y,int z,int number) { if(x<0||x>=n||y<0||y>=m||z<0||z>1||flag==1||number>num||number>=step[z][x][y]) return; if(a[z][x][y]=='*') return; if((abs(xx-x)+abs(yy-y))>(num-number)) return; if(x==xx&&y==yy&&z==zz&&number<=num) { flag=1; return; } if(a[z][x][y]=='#') { step[z][x][y]=number; dfs(x,y,1-z,number); return; } else { step[z][x][y]=number; dfs(x+1,y,z,number+1); dfs(x-1,y,z,number+1); dfs(x,y+1,z,number+1); dfs(x,y-1,z,number+1); return; } } int main() { int t=0; scanf("%d",&t); while(t--) { memset(a,'.',sizeof(a[0][0])); memset(step,0,sizeof(step[0][0])); num=0; scanf("%d%d%d",&n,&m,&num); for(int i=0;i<n;i++) { scanf("%s",&a[0][i]); getchar(); } getchar(); for(int i=0;i<n;i++) { scanf("%s",&a[1][i]); getchar(); } for(int l=0;l<2;l++) for(int i=0;i<n;i++) for(int j=0;j<m;j++) { step[l][i][j]=INT_MAX; if(a[l][i][j]=='P') { xx=i; yy=j; zz=l; } } flag=0; dfs(0,0,0,0); if(flag) printf("YES\n"); else printf("NO\n"); } }