Nightmare(搜索)
Nightmare(搜索)
1944864971 发表于2年前
Nightmare(搜索)
  • 发表于 2年前
  • 阅读 7
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

http://acm.hdu.edu.cn/showproblem.php?pid=1072

/*
题意:
迷宫内有入口和出口 在6分钟结束后炸弹会爆炸,但是迷宫内有重置炸弹的装置,可以重置炸弹的时间重新为6分钟
2代表入口,3代表出口 0代表墙 1代表路4代表重置炸弹的装置,每移动一步花费一分钟
求 走出迷宫的 最少移动步数 若不能走出迷宫输出-1;

分析:
与以往做的搜索题目有点不一样 此题可以走已经走过的路线 例如:直接走不能到达出口,但是旁边有一个4 可以先去走4增加时间 再回头接着走
这样时间增加了,

*/重生的一题

include

include

using namespace std;
int miGong[10][10];
int dir[4][2]={0,1,1,0,0,-1,-1,0};
struct node
{
int x;
int y;
int time;
int s;
};
int bfs(int startX,int startY,int m,int n)
{
queue q;
node a;
a.x=startX;
a.y=startY;
a.s=0;
a.time=6;
q.push(a);
while(q.size())
{
a=q.front();
q.pop();
if(miGong[a.x][a.y]==3)return a.s;//走到出口了
if(a.time==1)continue;//因为如果是在零时走到出口也会爆炸,逃亡失败
for(int i=0;i<4;i++)
{
int tx=a.x+dir[i][0];
int ty=a.y+dir[i][1];
if(tx<1||tx>m||ty<1||ty>n)
continue;
if(miGong[tx][ty]!=0)
{
node b;
b.x=tx;
b.y=ty;
b.s=a.s+1;
if(miGong[tx][ty]==4)//重置炸弹的这一步不能重复走,因为这是一次性的,用过一次就不能再用了
{ //如果走了这一步增加时间尚不能到达出口,那么第二次走的时候不能增加时间更不能到达出口了
b.time=6;
miGong[tx][ty]=0;
}
else b.time=a.time-1;
q.push(b);
}
}

}
return -1;

}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m,n;
int startX,startY;
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&miGong[i][j]);
if(miGong[i][j]==2)
{
startX=i;
startY=j;
}
}
printf("%d\n",bfs(startX,startY,m,n));
}
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: