a星

只是用一个二维状态数组,结果迂回搜索导致超时.

/?pid=4198

QuickoutoftheHarbour

ProblemDescription

题目原文是英文的，而且比较繁琐。我修饰转述如下：

小强被海盗抓到了，海盗把他和他的船“小强号”关在一个水狱里。

小强拿到了小红给他的一张水狱地图，地图由h行w列字符组成(3<=h;w<=500),，字符共有四种：

S：小强和他的“小强号”的起始位置，他要从这里逃跑。

#：不能逾越的石墙

.：水道，小强号可以直接通过

@：栅栏水道

已知：

小强打开栅栏需要d分钟(0<=d<=50)；

小强号通过单位水道的时间为1分钟；

水狱一定有出口。

输入：

t(一共有t组测试数据)

hwd以及水狱地图(每组测试数据输入一次)

输出：

小强出狱的最短时间（和路线）。

SampleInput

2

657

#

#S..#

#@#.#

#...#

#@###

#.###

453

#

#S#.##@..#

###@#

SampleOutput

1611

分析：

从S点开始，广度优先搜索，寻找出口。

由于有栅栏，不能保证搜索的当前结点是“耗时最少”的优先搜索，对当前结点耗时v取权重，采用优先队列。

code：（普通广度搜索，超时）

#include

#include

usingnamespacestd;#defineN501

#definebig999999999

inth,w,d,sx,sy,t,i,j;

inttv[N][N];charmaze[N][N];

intofft[4][2]={{-1,0},{0,-1},{1,0},{0,1}};structpos

{intx;inty;};

intbfs(){

intmymin=big;

posstart,temp,temp1;

start.x=sx,start.y=sy;

tv[sx][sy]=0;

queueq;

(start);

while(!())

{

temp=();();

if(temp.x==0||temp.x==h-1||temp.y==0||temp.y==w-1)if(mymin>tv[temp.x][temp.y]+1)

mymin=tv[temp.x][temp.y]+1;

printf("path:%d%d%cn",temp.x,temp.y,maze[temp.x][temp.y]);

for(i=0;i<4;i++){

postemp1;

temp1.x=temp.x+offt[i][0];

temp1.y=temp.y+offt[i][1];

if(temp1.x<0||temp1.x>=h||temp1.y<0||temp1.y>=w)continue;

if(maze[temp1.x][temp1.y]=='.')

if(tv[temp1.x][temp1.y]>tv[temp.x][temp.y]+1){

tv[temp1.x][temp1.y]=tv[temp.x][temp.y]+1;

(temp1);}

if(maze[temp1.x][temp1.y]=='@')

if(tv[temp1.x][temp1.y]>tv[temp.x][temp.y]+d+1)

{tv[temp1.x][temp1.y]=tv[temp.济南哪里好玩 x][temp.y]+1+d;(tem

p1);}

}}

returnmymin;}

intmain(){

cin>>t;while(t--)

{

cin>>h>>w>>d;

getchar();

for(i=0;i

for身份证照片可以化妆吗 (j=0;j

{

scanf("%c",&maze[i][j]);//cin百合多少钱一斤 >>maze[i][j];tv[i][j]=big;

if(maze[i][j]=='S')

{sx=i;sy=j;}}

getchar();

}

printf("%dn",bfs());//cout<

}}

code：改用优先队列，以到达该结点的时间v为权重，每次使v最小的结点出队，即所谓“A算法”

#include

#include

usingnamespacestd;#defineN501

inth,w,d,sx,sy,t,i,j;

boolud[N][N];charmaze[N][N];

intofft[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//方向数组

structpos

{intx;inty;intv;};

structcm什么是寓言故事 p//这样之后出队序列就是由小到大，搜索结点时优先搜索v（从S到当前结点耗费的时间）小的

结点。

{

booloperator()(constpos&p1,constpos&p2)

returnp1.v>p2.v;};

intbfs(){

posstart,temp,temp1;//start为搜索起点，temp为当前搜索的结点，temp1为当前结点的扩展

结点

start.x=sx,start.y=sy,start.v=0;

priority_queue,cmp>q;//注意拉,用优先级队列，小根堆

(start);

while(!())

{temp=();

();

//若temp结点从队列中出来，一定是水道或者栅栏，如果处于地图边缘，只要在该位置划船1分

钟就出水狱了

if(temp.x==0||temp.x==h-1||temp.y==0||temp.y==w-1)returntemp.v+1;

//对当前结点进行上下左右四个方向的搜索

for(i=0;i<4;i++){

postemp1;

temp1.x=temp.x+offt[i][0];temp1.y=temp.y+offt[i][1];

//拓展位置如果超过地图或者先前已经被搜索过，直接略过

if(ud[temp1.x][temp1.y]==1||temp1.x<0||temp1.x>=h||temp1.y<0||temp1.y>=w)

continue;

//拓展结点为"."水道,可以入队

if(maze[temp1.x][temp1.y]=='.'){

temp1.v=temp.v+1;(temp1);

ud[temp1.x][temp1.y]=1;}

//拓展结点temp1为“@”栅栏，可以入队，入队时已经算好从S到temp1的时间temp1.v

if(maze[temp1.x][temp1.y]=='@'){

temp1.v=temp.v+1+d;(temp1);

ud[temp1.x][temp1.y]=1;

}

}

}}

intmain(){

cin>>t;

while(t--){

cin>>h>>w>>d;

getchar();//为了在后面使用scanf读入字符,解决换行问题

for(i=0;i

for(j=0;j

scanf("%c",&maze[i][j]);ud[i][j]=0;

if(maze[i][j]=='S')

{sx=i;sy=j;}}

getchar();//为了使用scanf读入字符,解决换行问题}

printf("%dn",bfs());}

}

code：A*算法

在A算法基础上做改进，对结点以预测总耗费时间作为权重按由小到大排序。

预测总耗费时间=当前耗费时间+预期最小耗费时间。

预期最小耗费时间=该结点距离地图最近边缘的距离。

只需要在源代码上修改队列排序函数：cmp

intmymin(inta,intb,intc,intd){

a=a

return(a

structcmp{

booloperator()(constpos&p1,constpos&p2)

{return

(p1.v+mymin(p1.x,p1.y,h-1-p1.x,w-1-p1.y)>p2.v+mymin(p2.x,p2.y,h-1-p2.x,w-1-p2.y));}

};

code：在A算法基础上打印路径

#include

#include

usingnamespacestd;#defineN501

inth,w,d,sx,sy,t,i,j,ex,ey;structpos

{intx;inty;intv;};

intofft[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//方向数组upleftdownright

boolud[N][N];

charmaze[N][N];poslastp[N][N];

structcmp//这样之后出队序列就是由小到大，搜索结点时优先搜索v（从S到当前结点耗费的时间）小的

结点。{

booloperator()(constpos&p1,constpos&p2)

{return(p1.v>p2.v);}};

intbfs(){

posstart,temp,temp1;//start为搜索起点，temp为当前搜索的结点，temp1为当前结点的扩展

结点

start.x=sx,start.y=sy,start.v=0;

priority_queue,cmp>q;//注意拉,用优先级队列，小根堆

(start);

while(!())

{

temp=();();

//若temp结点从队列中出来，一定是水道或者栅栏，如果处于地图边缘，只要在该位置划船1分

钟就出水狱了

if(temp.x==0||temp.x==h-1||temp.y==0||temp.y==w-1){

ex=temp.x;

ey=temp.y;

returntemp.v+1;}

//对当前结点进行上下左右四个方向的搜索for(i=0;i<4;i++)

{

postemp1;

temp1.x=temp.x+offt[i][0];

temp1.y=temp.y+offt[i][1];

//拓展位置如果超过地图或者先前已经被搜索过，直接略过

if(ud[temp1.x][temp1.y]==1||temp1.x<0||temp1.x>=h||temp1.y教师个人简介 <0||temp1.y>=w)

continue;

//拓展结点为"."水道,可以入队

if(maze[temp1.x][temp1.y]=='.'){

temp1.v=temp.v+1;(temp1);

ud[temp1.x][temp1.y]=1;

lastp[temp1.x][temp1.y].x=temp.x;

lastp[temp1.x][temp1.y].y=temp.y;

lastp[temp1.x][temp1.y].v=temp1.v;}

//拓展结点temp1为“@”栅栏，可以入队，入队时已经算好从S到temp1的时间temp1.v

if(maze[temp1.x][temp1.y]=='@'){

temp1.v=temp.v+1+d;(temp1);

ud[temp1.x][temp1.y]=1;

lastp[temp1.x][temp1.y].x=temp.x;

lastp[temp1.x][temp1.y].y=temp.y;

lastp[temp1.x][temp1.y].v=temp1.v;

}

}

}}

voidshow(){

printf("thepath:n");

cout<

i=ex,j=ey;

while(maze[i][j]!='S')//(!(i==sx&&j==sy)){

maze[i][j]='';

cout<

intii,jj;ii=i;jj=j;

i=lastp[ii][jj].x;

j=lastp[ii][jj].y;}

printf("theroute:n");

for(i=0;i

for(j=0;j

cout<

}

cout<

cout<

intmain(){

cin>>t;

while(t--){

cin>>h>>w>>d;

getchar();//为了在后面使用scanf读入字符,解决换行问题

for(i=0;i

for(j=0;j

ud[i][j]=0;

for(i=0;i

for(j=0;j

scanf("%c",&maze[i][j]);

ud[i][j]=0;

if(maze[i][j]=='S')

{sx=i;sy=j;}}

getchar();//为了使用scanf读入字符,解决换行问题}

printf("theshortesttime:%dn",bfs());

show();

}

}

/*

2

657

#

#S..#

#@#.##...#

#@###

#.###

theshortesttime:16

thepath:

51

62

52

42

43

44

3424

23

theroute:

#

#S#

#@##

##

####

####

453

#

#S#.##@..#

###@#

theshortesttime:11

thepath:

33

44

3433

32

theroute:

#

#S#.#

##

####

*/

网上转的priority_queue用法的例子转自

/s/blog_

STL之优先队列

原本以为priority_queue很简单，才知道原来懂的只是最简单的形式。

头文件：#include

优先队列，也就是原来我们学过的堆，按照自己定义的优先级出队时。默认情况下底层是以Vector

实现的heap。

既然是队列，也就只有入队、出队、判空、大小的操作，并不具备查找功能。

函数列表：

empty()如果优先队列为空，则返回真

pop()删除第一个元素

push()加入一个元素

size()返回优先队列中拥有的元素的个数

top()返回优先队列中有最高优先级的元素

用途就不用多说了吧，例如Huffman编码、分支限界、A*启发式都需要用到优先队列存放信息。

来看最常用的几个功能，了解一下其中的知识点：

一：最基本的功能

#include

#include优先队列最基本的功能就是出队时不是

usingnamespacestd;按照先进先出的规则，而是按照队列中优

intmain()先级顺序出队。

{知识点：1、一般存放实型类型，可比较

priority_queueQ;大小

(2);2、默认情况下底层以Vector实现

(5);3、默认情况下是大顶堆，也就是大者优

(3);先级高，后面可以自定义优先级比较规则

while(!())

{

cout<<()<

();

}

system(百合什么意思 "pau");

return0;

}

二：次基本的功能

#include可以将一个存放实型类型的数据结构转

#include化为优先队列，这里跟优先队列的构造函

usingnamespacestd;数相关。

intmain()上面那个默认构造一个空的优先队列，什

{么都使用默认的。

inta[5]={3,4,5,2,1};而这里使用的是

priority_queueQ(a,a+5);Priority_queue(InputIterator

while(!())first,InputIteratorlast)

{我理解的就是给出了一个容器的开口和

cout<<()<

();现(默认vector)中去构造出优先队列。这

}里也使用了一个默认的比较函数，也是默

system("pau");认大顶堆

return0;

}

三应该掌握的功能:

#include

#include

usingnamespacestd;

typedefpairNode;

priority_queue,greater<

Node>>Q;

这个里面定义了一个制定存放

元素(Node),底层实现以vector

实现（第二个参数）,优先级为

小顶堆(第三个参数)。

前两个参数没什么说的，很好

理解，其中第三个参数，默认

有三写法：

小顶堆：greater

大顶堆：less

如果想自定义优先级而TYPE

不是基本类型，而是复杂类型，

例如结构体、类对象，则必须

重载其中的operator()，见下面

的例子。

例子：

#include

#include

usingnamespacestd;

//模拟存放节点信息

typedefstruct

{

inta;

intb;

}Node;

//自定义优先级类型

structcmp

{

booloperator()(constNode&t1,constNode&t2)

{

returnt1.b

}

};

intmain()

{

//初始化

intn;

cin>>n;

Node*arr=newNode[n];

for(inti=0;i

{

cin>>arr[i].a>>arr[i].b;

}

//定义优先队列，自定义优先级,跟Qso怎么办签证和护照 rt里面自定义相似

priority_queue,cmp>Q(arr,arr+n);

while(!())

{

Noden=(厉害英语 );

cout<

();

}

system("pau");

return0;

}