程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2102 A計劃 BFS

HDU 2102 A計劃 BFS

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved