编程开发 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
移动开发 架构设计 编程语言 互联网 开发经验 Web前端 开发总结
开发杂谈 系统运维 研发管理 数据库 云 计 算 Java开发
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
  编程开发知识库 -> 编程语言 -> HDOJ/HDU 1180 诡异的楼梯(经典BFS -> 正文阅读
 

[编程语言]HDOJ/HDU 1180 诡异的楼梯(经典BFS[第1页]


Problem Description
Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的,相反,他们每隔一分钟就变动一次方向.
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的.
Input
测试数据有多组,每组的表述如下:
第一行有两个数,M和N,接下来是一个M行N列的地图,’*’表示障碍物,’.’表示走廊,’|’或者’-‘表示一个楼梯,并且标明了它在一开始时所处的位置:’|’表示的楼梯在最开始是竖直方向,’-‘表示的楼梯在一开始是水平方向.地图中还有一个’S’是起点,’T’是目标,0<=M,N<=20,地图中不会出现两个相连的梯子.Harry每秒只能停留在’.’或’S’和’T’所标记的格子内.
Output
只有一行,包含一个数T,表示到达目标的最短时间.
注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.
Sample Input
5 5
**..T
**.*.
..|..
.*.*.
S....

Sample Output
7
Hint
Hint
地图如下:


挺经典的一个广搜题目!
题意很好理解。做的时候理清思路,注意楼梯的方向,楼梯的方向可以用到达时候的时间的奇偶来判断。因为楼梯只有2个方向!上下,或者左右。
移动到楼梯后面也还要判断下是否越界,楼梯对面是不是墙,是不是已经走过,这3个条件,满足了才能过去。
如果到的时候,楼梯方向与过去的方向不同,就只能等待一分钟,在这个时候,位置不动,时间加1!再进入队列。这个顺序很重要!
不能先过去,然后时间加2,再入队列。这样会超内存,这是很多人用优先队列的原因!
(因为这样的话,你会发现,弹出的node型变量的t会出现t-时间小的会在后面弹出,这样增加了内存的使用!!!)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct node{
    int x,y,t;
};
int n,m;
int mx[]={0,1,0,-1};
int my[]={1,0,-1,0};//右,下,左,上
char map[30][30];
int d[30][30];
int tx,ty,sx,sy;
node ft;
int judge(int x,int y){
    if(x<0||x>=n||y<0||y>=m){
        return 0;
    }
    if(d[x][y]){
        return 0;
    }
    if(map[x][y]=='*'){
        return 0;
    }
    return 1;
}


void bfs(){
    queue<node> q;
    ft.x=sx;
    ft.y=sy;
    ft.t=0;
    q.push(ft);
    d[sx][sy]=1;
    while(!q.empty()){
        node ff=q.front();
        q.pop();
        int x=ff.x;
        int y=ff.y;
        if(map[x][y]=='T'){
            printf("%d\n",ff.t);
            return;
        }
        for(int i=0;i<4;i++){
            x=ff.x+mx[i];
            y=ff.y+my[i];
            if(!judge(x,y)){
                continue;
            }
            node nt;
            if(map[x][y]=='.'||map[x][y]=='T'){//正常走
                nt.x=x;
                nt.y=y;
                nt.t=ff.t+1;
                d[nt.x][nt.y]=1;
                q.push(nt);
                continue;
            }else if(i==0||i==2){//右和左
                if(map[x][y]=='-'&&ff.t%2==0){//可以过去
                    nt.x=x+mx[i];
                    nt.y=y+my[i];
                    if(judge(nt.x,nt.y)){
                        nt.t=ff.t+1;
                        d[nt.x][nt.y]=1;
                        q.push(nt);
                    }
                }else if(map[x][y]=='|'&&ff.t%2!=0){
                    nt.x=x+mx[i];
                    nt.y=y+my[i];
                    if(judge(nt.x,nt.y)){
                        nt.t=ff.t+1;
                        d[nt.x][nt.y]=1;
                        q.push(nt);
                    }
                }else {//不能过楼梯,得等一分钟
                    nt.x=ff.x;
                    nt.y=ff.y;
                    nt.t=ff.t+1;
                    d[nt.x][nt.y]=1;
                    q.push(nt);
                }
            }else{//上和下
                if(map[x][y]=='|'&&ff.t%2==0){//可以过去
                    nt.x=x+mx[i];
                    nt.y=y+my[i];
                    if(judge(nt.x,nt.y)){
                        nt.t=ff.t+1;
                        d[nt.x][nt.y]=1;
                        q.push(nt);
                    }
                }else if(map[x][y]=='-'&&ff.t%2!=0){
                    nt.x=x+mx[i];
                    nt.y=y+my[i];
                    if(judge(nt.x,nt.y)){
                        nt.t=ff.t+1;
                        d[nt.x][nt.y]=1;
                        q.push(nt);
                    }
                }else {//不能过楼梯,得等一分钟
                    nt.x=ff.x;
                    nt.y=ff.y;
                    nt.t=ff.t+1;
                    d[nt.x][nt.y]=1;
                    q.push(nt);
                }
            }
        }
    }
}


int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(d,0,sizeof(d));
        for(int i=0;i<n;i++){
            scanf("%s",map[i]);
            for(int j=0;j<m;j++){
                if(map[i][j]=='S'){
                    sx=i,sy=j;
                }
            }
        }
        bfs();
    }
    return 0;
}


测试数据:
/*
3 3
S|.
-..
T..
5 5
**..T
**.*.
..|..
.*.*.
S....
3 4
S|.|
-T-.
.|..
20 20
S.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|.|.
.|.|.|.|.|.|.|.|.|.T
2 7 7 20
*/

  编程语言 最新文章
洛谷P3916 图的遍历_graph
Java_7
C#使用UdpClient发送和接收UDP数据示例 16进
php必会基础
Java判断是否为整数的5种方法
Socket 双向传输问题
腾讯手QQ核心技术-NDK开发语音消息变声功能
遍历枚举接口的元素
多线程-ThreadLocal
翻译 Spring Boot How To
上一篇文章      下一篇文章      查看所有文章
加:2016-07-11 15:36:20  更:2016-07-11 15:39:50 
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年7日历
2018-7-19 0:25:10
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程开发知识库