学步园

第三个BFS

题目大意:这个题是以坦克大战为原型出来的题目，就是走迷宫的变种，给定一个地图mxn的地图，地图上有普通的砖B，金砖S，河R，和一个宝物位置T，和你的位置Y，求吃到宝物的最小步数(坦克通过普通砖需要两步，不能通过金砖和河)...

Sample Input

3 4
YBEB
EERE
SSTE
0 0

Sample Output

8

思路：走迷宫的思路，加点变化，在将横纵坐标步数入队的同时在将stay入队，如果当前走的点是普通砖，stay就等于1,否则等于0,当这个点出队的时候如果stay=1就另stay=0，再入队一次。。实现了原地停留一步的效果。。。

#include<iostream><br /> using namespace std;<br /> struct mov<br /> {<br /> int x,y;<br /> }mov[4]={1,0,-1,0,0,1,0,-1};<br /> char map[310][310]; int m,n,lock[310][310],head,rear;<br /> int queue[1000000];<br /> int pop(){ return queue[head++%1000000]; }<br /> void push(int i){ queue[rear++%1000000]=i; }<br /> int bfs()<br /> {<br /> int i,j,stay,step,fang;<br /> while(head!=rear)<br /> {<br /> i=pop(); j=pop(); stay=pop(); step=pop();</p> <p> if(map[i][j]=='T') return step;</p> <p> if(stay)<br /> {<br /> push(i); push(j); push(stay-1); push(step+1);<br /> continue;<br /> }<br /> for(fang=0;fang<4;fang++)<br /> if(i+mov[fang].x>-1&&i+mov[fang].x<m&&j+mov[fang].y>-1&&j+mov[fang].y<n&&lock[i+mov[fang].x][j+mov[fang].y]==0&&map[i+mov[fang].x][j+mov[fang].y]!='R'&&map[i+mov[fang].x][j+mov[fang].y]!='S')<br /> {<br /> lock[i+mov[fang].x][j+mov[fang].y]=1;<br /> push(i+mov[fang].x); push(j+mov[fang].y);<br /> if(map[i+mov[fang].x][j+mov[fang].y]=='B')<br /> push(1);<br /> if(map[i+mov[fang].x][j+mov[fang].y]=='E'||map[i+mov[fang].x][j+mov[fang].y]=='T')<br /> push(0);<br /> push(step+1);<br /> }</p> <p> }<br /> return 0;<br /> }</p> <p>int main()<br /> {<br /> int i,j,o;<br /> while(cin>>m>>n&&m)<br /> {<br /> head=rear=0;<br /> memset(lock,0,sizeof(lock));<br /> for(i=0;i<m;i++)<br /> cin>>map[i];<br /> for(i=0;i<m;i++)<br /> for(j=0;j<n;j++)<br /> if(map[i][j]=='Y')<br /> goto start;<br /> start:<br /> lock[i][j]=1; push(i); push(j); push(0); push(0);<br /> o=bfs();<br /> if(o)<br /> cout<<o<<endl;<br /> else<br /> cout<<"-1"<<endl;<br /> }<br /> return 0;<br /> }