#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<cmath> #include<queue> using namespace std; int jz[20][20]={0};//存储原地图 struct NODE//一个节点,即一个状态 { int x,y,bs,xl;//位置,步数与血量 }qc,fr; int zl[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//增量,即向四周可能走的位置 int visit[20][20]={0};//visit int版数组 queue<NODE>wz;//bfs队列 int main() { int n,m; scanf("%d%d",&n,&m); int sx,sy; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&jz[i][j]); if(jz[i][j]==2)sx=i,sy=j;//记录出发位置 } wz.push((NODE){sx,sy,0,6});//推入队列,这里用了强制类型转换 visit[sx][sy]=6;//初始位置设置其visit值 bool tf=true;//判断是否完成任务,tf==false即完成 while(!wz.empty()&&tf)//直到完全失败或成功 { qc=wz.front();//取队列最前面的节点 wz.pop();//弹出队列 if(qc.xl==1)continue;//如果血量为1,则继续 for(int i=0;i<4&&tf;i++)//四个方向 { if(jz[qc.x+zl[i][0]][qc.y+zl[i][1]])//如果可以到达 if(visit[qc.x+zl[i][0]][qc.y+zl[i][1]]<qc.xl-1)//如果血量更大 { fr.x=qc.x+zl[i][0]; fr.y=qc.y+zl[i][1]; fr.bs=qc.bs+1;//更新新的节点 fr.xl=jz[fr.x][fr.y]==4?6:qc.xl-1;//如果下一个节点是有鼠标的,那么有变成6 visit[fr.x][fr.y]=qc.xl-1;//更新visit if(jz[fr.x][fr.y]==3)tf=false;//如果任务完成,那么tf更新 wz.push(fr);//加入队列 } } } if(tf)printf("-1");//如果任务失败 else printf("%d",fr.bs);//如果任务成功,则输出结果 return 0; } /************************************************************** Problem: 1914 User: admin Language: C++ Result: Accepted Time:24 ms Memory:2080 kb ****************************************************************/