相信坦克大戰(zhàn)大家都玩過吧，本題就是根據(jù)這個(gè)游戲設(shè)計(jì)的。坦克要從起點(diǎn)（Y），到目的地（T），坦克不能通過鋼墻（S），河（R），可以在空地在行走（E），射擊破壞磚墻（B），射擊磚墻時(shí)不行走且花費(fèi)一個(gè)單位的時(shí)間，在空地上行走時(shí)也花費(fèi)一個(gè)單位的時(shí)間。求坦克從起點(diǎn)到目的地最少花多少時(shí)間，不可達(dá)輸出－1；
很好的一道搜索題。因?yàn)榭紤]到通過磚墻時(shí)和空地所花的時(shí)間不同，所以不能使用一般的BFS廣搜來做。用DFS深搜，你會(huì)發(fā)現(xiàn)時(shí)間復(fù)雜非常高，必然會(huì)超時(shí)（最大是300＊300的圖）。本題可以使用改進(jìn)過的廣搜或優(yōu)先隊(duì)列＋bfs 或 記憶化廣搜三種方法來解決。
第一種方法：改進(jìn)過的BFS：
有些節(jié)點(diǎn)需要耗費(fèi)2個(gè)單位時(shí)間，要想用BFS就得改一下，由于BFS每次只能操作一步，要不就是擴(kuò)展，要不就是破壞磚墻。所以只需檢查該點(diǎn)是不是'B'，是的話就得停一步，不是的話，繼續(xù)擴(kuò)展，也就是說某些點(diǎn)的擴(kuò)展慢了一拍，所以從隊(duì)列里出來的點(diǎn)就判斷一下再看執(zhí)行哪個(gè)操作。
從這道題，我也對bfs有了更深的理解，“bfs之所以能最快找到最優(yōu)解，就是因?yàn)樗看尾僮饕徊剑ㄟ@里的操作一步，很靈活，例如題目中的破壞磚墻），而while（）里面的語句就是一次操作了！”
/*
這道題中B點(diǎn)需要操作兩步，所以遇到B點(diǎn)后不能+2后直接壓進(jìn)隊(duì)列，需要在原地停一下，不能擴(kuò)展到其他點(diǎn)，相當(dāng)于他只能擴(kuò)展到自身，所以就把自身壓進(jìn)隊(duì)列里map[x][y]='E'是因?yàn)槠茐拇u墻一次就夠了，不然下次，還是'B'，不斷壓進(jìn)隊(duì)列，不斷在原地停留
平常一般是考慮“入隊(duì)列” 的點(diǎn)，這次要考慮“出隊(duì)列” 的點(diǎn)是否滿足條件！
*/
#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
int x,y,time;
};
int bfs()
{
int i;
node you,start,next;
queue<node>q;
you.x=sx;
you.y=sy;
you.time=0;
q.push(you);
visit[sx][sy]=1;
while(!q.empty())
{
start=q.front();
q.pop();
if(map[start.x][start.y]=='B') //這一步需要停一停
{
start.time++;
map[start.x][start.y]='E';
q.push(start);
}
else
{
for(i=0;i<4;i++)
{
next.x=start.x+dir[i][0]; //搜索下一個(gè)點(diǎn)
next.y=start.y+dir[i][1];
if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y]) //判斷下一個(gè)點(diǎn)是否合法
continue;
next.time=start.time+1;
if(map[next.x][next.y]=='T') //到達(dá)目的地
return next.time;
visit[next.x][next.y]=1; //標(biāo)記已經(jīng)走過的點(diǎn)
q.push(next);
}
}
}
return -1;
}
int main(void)
{
int i,j;
while(scanf("%d %d",&m,&n)==2)
{
if(m==0 && n==0)
break;
memset(visit,0,sizeof(visit)); //初始化每個(gè)節(jié)點(diǎn)的狀態(tài)
for(i=0;i<m;i++)
{
getchar();
for(j=0;j<n;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='Y') //記錄起始點(diǎn)
{
sx=i;
sy=j;
}
}
}
printf("%d/n",bfs());
}
system("pause");
return 0;
}
第二種方法：優(yōu)先隊(duì)列＋BFS法
也是用到了廣搜的思想，只是在出隊(duì)時(shí)做了處理，利用優(yōu)先隊(duì)列讓隊(duì)列中到起點(diǎn)的時(shí)間值最小的點(diǎn)先出隊(duì)。該方法會(huì)用到優(yōu)先隊(duì)列的STL。
首先需要了解優(yōu)先隊(duì)列的使用規(guī)則：
優(yōu)先隊(duì)列中元素的比較規(guī)則默認(rèn)是按元素的值從大到小排序的，就是說隊(duì)列中最大的元素總是位于隊(duì)首，所以出隊(duì)時(shí)，并非按先進(jìn)先出的原則進(jìn)行，而是將當(dāng)前隊(duì)列中最大的元素出隊(duì)。這點(diǎn)類似于給隊(duì)列里的元素進(jìn)行了從大到小的排序。當(dāng)然，可以通過重載“<”操作符來重新定義比較規(guī)則。
重載“<”操作符的函數(shù)可以寫在結(jié)構(gòu)體里面，也可以寫在結(jié)構(gòu)體外面，寫在結(jié)構(gòu)體外面的時(shí)候，記得函數(shù)的參數(shù)要使用引用。。
第一種重載方法：
struct node
{
int x,y;
int step;
};
priority_queue<node>q; //優(yōu)先隊(duì)列中元素的比較規(guī)則默認(rèn)是按元素的值從大到小排序；
bool operator<(const node &a,const node &b) //括號(hào)里面是const 而且還必須是引用
{
return a.step>b.step; //從小到大排序。重載小于號(hào)。因?yàn)槟J(rèn)是從大到小
}
第二種重載方法：
struct node
{
int x,y;
int time; //定義一個(gè)優(yōu)先隊(duì)列
friend bool operator<(node a, node b)
{ //從小到大排序采用“>”號(hào)；如果要從大到小排序，則采用“<”號(hào)
return a.time> b.time; //從小到大排序
}
};
priority_queue<node>q; //優(yōu)先隊(duì)列中元素的比較規(guī)則默認(rèn)是按元素的值從大到小排序；
切記：從小到大排序采用“>”號(hào)；如果要從大到小排序，則采用“<”號(hào)；
/*
優(yōu)先隊(duì)列的實(shí)現(xiàn)就不用局限每次操作一步了，但每次都取最小操作次數(shù)的步來走
*/
#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
int x,y,time; //定義一個(gè)優(yōu)先隊(duì)列
friend bool operator<(node a, node b)
{
return a.time> b.time; //從小到大排序
}
};
int bfs()
{
int i;
node you,start,next;
priority_queue<node>q;
you.x=sx;
you.y=sy;
you.time=0;
q.push(you);
visit[sx][sy]=1;
while(!q.empty())
{
start=q.top(); //取隊(duì)頭指針與普通隊(duì)列不同（Q.front）
q.pop();
for(i=0;i<4;i++)
{
next.x=start.x+dir[i][0]; //搜索下一個(gè)點(diǎn)
next.y=start.y+dir[i][1];
if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y]) //判斷下一個(gè)點(diǎn)是否合法
continue;
if(map[next.x][next.y]=='B') //注意此處不要馬虎
next.time=start.time+2;
else
next.time=start.time+1;
if(map[next.x][next.y]=='T') //到達(dá)目的地
return next.time;
visit[next.x][next.y]=1; //標(biāo)記已經(jīng)走過的點(diǎn)
q.push(next);
}
}
return -1;
}
int main(void)
{
int i,j;
while(scanf("%d %d",&m,&n)==2)
{
if(m==0 && n==0)
break;
memset(visit,0,sizeof(visit)); //初始化每個(gè)節(jié)點(diǎn)的狀態(tài)
for(i=0;i<m;i++)
{
getchar();
for(j=0;j<n;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='Y') //記錄起始點(diǎn)
{
sx=i;
sy=j;
}
}
}
printf("%d/n",bfs());
}
system("pause");
return 0;
}
第三種方法：記憶化廣搜
和優(yōu)先隊(duì)列BFS在出隊(duì)時(shí)做處理不同的是，記憶化廣搜是在點(diǎn)入隊(duì)是做處理。記憶化廣搜時(shí)不必要對點(diǎn)進(jìn)行標(biāo)記，只是在入隊(duì)是注意選擇。比如若搜到A點(diǎn)時(shí)，要選擇比A點(diǎn)時(shí)間值大的鄰接點(diǎn)入隊(duì)（不能相等），并更新入隊(duì)點(diǎn)的時(shí)間值。
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
int co,ro,mi,step[305][305];
char map[305][305],visited[305][305];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
typedef struct node
{
int x;
int y;
int time;
}node;
bool judge(int x,int y)
{
if(x<0||y<0||x>=co||y>=ro)
{
return false;
}
if(map[x][y]=='S'||map[x][y]=='R')
{
return false;
}
return true;
}
void bfs(int a,int b)
{
int i,x,y,ti;
node in,out;
queue<node>que;
in.x=a;
in.y=b;
step[a][b]=0;
que.push(in);
while(!que.empty())
{
out=que.front();
que.pop();
visited[out.x][out.y]=0;
for(i=0;i<4;i++)
{
x=out.x+dir[i][0];
y=out.y+dir[i][1];
if(!judge(x,y))
continue;
ti=step[out.x][out.y]+1;
if(map[x][y]=='B')
ti++;
if(step[x][y]<=ti)
continue;
step[x][y]=ti;
if(visited[x][y])
continue;
visited[x][y]=1;
in.x=x;
in.y=y;
que.push(in);
}
}
}
int main()
{
int i,j,a,b,c,d;
while(scanf("%d %d",&co,&ro),co+ro)
{
getchar();
for(i=0;i<co;i++)
gets(map[i]);
for(i=0;i<co;i++)
for(j=0;j<ro;j++)
{
if(map[i][j]=='Y')
{
a=i;
b=j;
}
if(map[i][j]=='T')
{
c=i;
d=j;
}
step[i][j]=999999;
}
memset(visited,0,sizeof(visited));
visited[a][b]=1;
bfs(a,b);
if(step[c][d]!=999999)
printf("%d/n",step[c][d]);
else
printf("-1/n");
}
return 0;
}
