HDU 2102 A計劃 BFS

點擊打開鏈接

A計劃

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10939 Accepted Submission(s): 2667


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

Source HDU 2007-6 Programming Contest 直接廣搜，不過有幾處坑點：
1.起點是（0，0，0）
2.時間小於等於t都可以
3.第一層和第二層都是“#”，那麼這個點跟第二層是“*”結果是一樣的。

//0MS	1464K
#include
#include
#include
using namespace std;
int n,m,t,sx,sy,ex,ey,sz,ez;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int vis[2][17][17];
char g[2][17][17];
struct sa
{
    int x,y,z,s;
};
int bfs()
{
    queueq;
    memset(vis,0,sizeof(vis));
    sa now,next;
    now.z=0;now.x=0;now.y=0;now.s=0;
    vis[sz][sx][sy]=1;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.z==ez&&now.x==ex&&now.y==ey)
        {
            if(now.s<=t)return 1;
            return -1;
        }
        for(int i=0;i<4;i++)
        {
            int xx=now.x+dir[i][0];
            int yy=now.y+dir[i][1];
            int zz=now.z;
            if(xx>=0&&xx=0&&yy