A计划
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7258 Accepted Submission(s): 1710
Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是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
Source
Recommend
xhd
首先拿到这个题目不要想太多，既然是求最短步骤，那么一般都能想到BFS，这个题目的BFS和其他题目的BFS并没有什么太大的区别
不过要注意初始化和几点细节
初始化的时候如果两层同时是#那么就都变成*，这样防止程序陷入死循环，个人猜想这样的测试数据也不会给
如果两层有一边是墙一边是穿梭机，那么统一变成墙，因为不能让勇士死
rec_up 和 rec_down 是用来记录当前要搜索的位置是否搜索过了，其实我是这样的，这两个数组用来记录经过这个点的最小步骤
如果下一次又碰到这个点，那么就判断现在到这个点的步骤是否比历史最短的更短，否则就跳过这个点，符合则重新搜索这个点
还要注意的就是几个小剪枝，这个不多说了，刚才判断就是一个小剪枝，还有时间不能大于COUNT。
由于情况比较多，所以代码好像有点长，不过没关系，没什么太多的技术含量！
这个题目数据量比较小，一般结果对了差不多都能通过。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define count COUNT
using namespace std;
struct point
{
int i,j;
int num;
bool up_down;
};
int n,m,count;
char map_up[15][15];
char map_down[15][15];
int rec_up[15][15];
int rec_down[15][15];
int init()
{
int i,j;
for(i=0;i<=m+1;i++)
{
map_up[0][i]='*',map_down[0][i]='*';
map_up[n+1][i]='*',map_down[n+1][i]='*';
}
for(i=0;i<=n+1;i++)
{
map_up[i][0]='*',map_down[i][0]='*';
map_up[i][m+1]='*',map_down[i][m+1]='*';
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
rec_up[i][j]=rec_down[i][j]=999999;
if(map_up[i][j]=='#' && (map_down[i][j]=='#' || map_down[i][j]=='*'))
map_up[i][j]=map_down[i][j]='*';
if(map_down[i][j]=='#' && (map_up[i][j]=='#' || map_up[i][j]=='*'))
map_up[i][j]=map_down[i][j]='*';
}
return 0;
}
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
bool flag=true;
int BFS()
{
queue<point> q;
point temp;
point p;
flag=true;
int i;
//memset(rec_up,0,sizeof(rec_up));
//memset(rec_down,0,sizeof(rec_down));
temp.i=1,temp.j=1,temp.num=0;
if(map_up[1][1]=='#')
temp.up_down=false;
else
temp.up_down=true;
q.push(temp);
while(!q.empty())
{
temp=q.front();
q.pop();
if(flag==false)
return 0;
if(temp.up_down)
{
if(map_up[temp.i][temp.j]=='P')
{
flag=false;
printf("YES\n");
return 0;
}
}
else
{
if(map_down[temp.i][temp.j]=='P')
{
flag=false;
printf("YES\n");
return 0;
}
}
if(temp.num >= count)
return 0;
for(i=0;i<4;i++)
{
p=temp;
if(p.up_down)
{
if(map_up[p.i+dir[i][0]][p.j+dir[i][1]]=='.' && rec_up[p.i+dir[i][0]][p.j+dir[i][1]] > p.num+1)
{
rec_up[p.i+dir[i][0]][p.j+dir[i][1]]=p.num+1;
p.num++;
p.i=p.i+dir[i][0],p.j=p.j+dir[i][1];
q.push(p);
}
else if(map_up[p.i+dir[i][0]][p.j+dir[i][1]]=='#' && rec_down[p.i+dir[i][0]][p.j+dir[i][1]] > p.num+1)
{
p.num++;
p.up_down=false;
rec_down[p.i+dir[i][0]][p.j+dir[i][1]]=p.num;
p.i=p.i+dir[i][0],p.j=p.j+dir[i][1];
q.push(p);
}
else if((map_up[p.i+dir[i][0]][p.j+dir[i][1]]=='P'))
{
printf("YES\n");
flag=false;
return 0;
}
}
else
{
if(map_down[p.i+dir[i][0]][p.j+dir[i][1]]=='.' && rec_down[p.i+dir[i][0]][p.j+dir[i][1]] > p.num+1)
{
rec_down[p.i+dir[i][0]][p.j+dir[i][1]]=p.num+1;
p.num++;
p.i=p.i+dir[i][0],p.j=p.j+dir[i][1];
q.push(p);
}
else if(map_down[p.i+dir[i][0]][p.j+dir[i][1]]=='#' && rec_up[p.i+dir[i][0]][p.j+dir[i][1]] > p.num+1)
{
p.num++;
p.up_down=true;
rec_up[p.i+dir[i][0]][p.j+dir[i][1]]=p.num;
p.i=p.i+dir[i][0],p.j=p.j+dir[i][1];
q.push(p);
}
else if((map_down[p.i+dir[i][0]][p.j+dir[i][1]]=='P'))
{
printf("YES\n");
flag=false;
}
}
}
}
return 0;
}
int main()
{
int t;
int i;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&count);
for(i=1;i<=n;i++)
scanf("%s",map_up[i]+1);
for(i=1;i<=n;i++)
scanf("%s",map_down[i]+1);
init();
BFS();
if(flag)
printf("NO\n");
}
return 0;
}